fork(1) download
copy 
  1. #include <vector>
  2. #include <list>
  3. #include <map>
  4. #include <set>
  5. #include <deque>
  6. #include <queue>
  7. #include <stack>
  8. #include <bitset>
  9. #include <algorithm>
  10. #include <functional>
  11. #include <numeric>
  12. #include <utility>
  13. #include <sstream>
  14. #include <iostream>
  15. #include <iomanip>
  16. #include <cstdio>
  17. #include <cmath>
  18. #include <cstdlib>
  19. #include <cctype>
  20. #include <string>
  21. #include <cstring>
  22. #include <cstdio>
  23. #include <cmath>
  24. #include <cstdlib>
  25. #include <ctime>
  26. #include <string.h>
  27. #include <fstream>
  28. #include <cassert>
  29. using namespace std;
  30.  
  31. #define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
  32. #define sz(a) int((a).size())
  33. #define rep(i, s, n)  for(int i = s; i <= (n); ++i)
  34. #define rev(i, n, s)  for(int i = (n); i >= s; --i)
  35. #define fore(x, a) for(auto &&x : a)
  36. typedef long long ll;
  37. const int mod = 1000000007;
  38. const int N = 655;
  39.  
  40. typedef long double DOUBLE;
  41. typedef vector<DOUBLE> VD;
  42. typedef vector<VD> VVD;
  43. typedef vector<int> VI;
  44. const DOUBLE EPS = 1e-9;
  45. struct LPSolver {
  46.   int m, n;
  47.   VI B, N;
  48.   VVD D;
  49.   LPSolver(const VVD &A, const VD &b, const VD &c) :
  50.     m(b.size()), n(c.size()), N(n + 1), B(m), D(m + 2, VD(n + 2)) {
  51.     for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) D[i][j] = A[i][j];
  52.     for (int i = 0; i < m; i++) { B[i] = n + i; D[i][n] = -1; D[i][n + 1] = b[i]; }
  53.     for (int j = 0; j < n; j++) { N[j] = j; D[m][j] = -c[j]; }
  54.     N[n] = -1; D[m + 1][n] = 1;
  55.   }
  56.   void Pivot(int r, int s) {
  57.     for (int i = 0; i < m + 2; i++) if (i != r)
  58.       for (int j = 0; j < n + 2; j++) if (j != s)
  59.         D[i][j] -= D[r][j] * D[i][s] / D[r][s];
  60.     for (int j = 0; j < n + 2; j++) if (j != s) D[r][j] /= D[r][s];
  61.     for (int i = 0; i < m + 2; i++) if (i != r) D[i][s] /= -D[r][s];
  62.     D[r][s] = 1.0 / D[r][s];
  63.     swap(B[r], N[s]);
  64.   }
  65.   bool Simplex(int phase) {
  66.     int x = phase == 1 ? m + 1 : m;
  67.     while (true) {
  68.       int s = -1;
  69.       for (int j = 0; j <= n; j++) {
  70.         if (phase == 2 && N[j] == -1) continue;
  71.         if (s == -1 || D[x][j] < D[x][s] || D[x][j] == D[x][s] && N[j] < N[s]) s = j;
  72.       }
  73.       if (D[x][s] >= -EPS) return true;
  74.       int r = -1;
  75.       for (int i = 0; i < m; i++) {
  76.         if (D[i][s] <= 0) continue;
  77.         if (r == -1 || D[i][n + 1] / D[i][s] < D[r][n + 1] / D[r][s] ||
  78.           D[i][n + 1] / D[i][s] == D[r][n + 1] / D[r][s] && B[i] < B[r]) r = i;
  79.       }
  80.       if (r == -1) return false;
  81.       Pivot(r, s);
  82.     }
  83.   }
  84.   DOUBLE Solve(VD &x) {
  85.     int r = 0;
  86.     for (int i = 1; i < m; i++) if (D[i][n + 1] < D[r][n + 1]) r = i;
  87.     if (D[r][n + 1] <= -EPS) {
  88.       Pivot(r, n);
  89.       if (!Simplex(1) || D[m + 1][n + 1] < -EPS) return -numeric_limits<DOUBLE>::infinity();
  90.       for (int i = 0; i < m; i++) if (B[i] == -1) {
  91.         int s = -1;
  92.         for (int j = 0; j <= n; j++)
  93.           if (s == -1 || D[i][j] < D[i][s] || D[i][j] == D[i][s] && N[j] < N[s]) s = j;
  94.         Pivot(i, s);
  95.       }
  96.     }
  97.     if (!Simplex(2)) return numeric_limits<DOUBLE>::infinity();
  98.     x = VD(n);
  99.     for (int i = 0; i < m; i++) if (B[i] < n) x[B[i]] = D[i][n + 1];
  100.     return D[m][n + 1];
  101.   }
  102. };
  103.  
  104. int a[N];
  105.  
  106. int main() {
  107. #ifdef loc
  108.   if(!freopen((string(FOLDER) + "inp.txt").c_str(), "r", stdin)) {
  109.     assert(0);
  110.   }
  111.   freopen((string(FOLDER) + "out.txt").c_str(), "w", stdout);
  112. #endif
  113.   boost;
  114.   int n, k;
  115.   cin >> n >> k;
  116.   n *= 3;
  117.   int m = n + n - n / 3 + 1;
  118.   rep(i, 0, n - 1) {
  119.     cin >> a[i];
  120.   }
  121.   VVD A(m, VD(n,0.0));
  122.   VD B(m,0.0);
  123.   VD C(n, 0.0);
  124.   rep(i, 0, n - 1) {
  125.     C[i] = a[i];
  126.   }
  127.   rep(i, 0, n - n / 3) {
  128.     rep(j, i, i + n/3 - 1) {
  129.       A[i][j] = 1.0;
  130.     }
  131.     B[i] = k;
  132.   }
  133.   rep(i, 0, n - 1) {
  134.     A[i + n - n / 3 + 1][i] = 1.0;
  135.     B[i + n - n / 3 + 1] = 1.0;
  136.   }
  137.   VD X;
  138.   LPSolver solver(A, B, C);
  139.   double val = solver.Solve(X);
  140.   int res = (int)(val + 0.5);
  141.   cout << res << endl;
  142.   return 0;
  143. }
Success #stdin #stdout 0s 3592KB
comments (?)
stdin
copy 
5 3
14 21 9 30 11 8 1 20 29 23 17 27 7 8 35
stdout
copy 
195
https://ideone.com/dVn1wb
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!