fork(2) download
copy 
  1. #include <set>
  2. #include <map>
  3. #include <list>
  4. #include <cmath>
  5. #include <queue>
  6. #include <stack>
  7. #include <cstdio>
  8. #include <string>
  9. #include <vector>
  10. #include <cstdlib>
  11. #include <cstring>
  12. #include <sstream>
  13. #include <iomanip>
  14. #include <complex>
  15. #include <iostream>
  16. #include <algorithm>
  17.  
  18. #include <ctime>
  19. #include <deque>
  20. #include <bitset>
  21. #include <cctype>
  22. #include <utility>
  23. #include <cassert>
  24. using namespace std;
  25.  
  26. #define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
  27. #define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
  28. #define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
  29. #define EACH(it,a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it)
  30. #define SZ(S) ((int) ((S).size()))
  31.  
  32. #define DEBUG(x) { cout << #x << " = " << x << endl; }
  33. #define PR(a,n) { cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl; }
  34. #define PR0(a,n) { cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl; }
  35.  
  36. int n;
  37. struct Alloy {
  38.     int c, in, out;
  39. } a[1500];
  40. bool operator < (const Alloy &a, const Alloy &b) { return a.c < b.c; }
  41. int nAlloy;
  42. int f[1500][1500][2];
  43.  
  44. void update(int &x, int val) {
  45.     if (x < 0) x = val;
  46.     else x = min(x, val);
  47. }
  48.  
  49. int main() {
  50.     while (scanf("%d", &n) == 1) {
  51.         nAlloy = 0;
  52.         memset(f, -1, sizeof f);
  53.         FOR(i,1,n) FOR(j,1,n) {
  54.             int x, y; scanf("%d.%d", &x, &y);
  55.             if (i < j) {
  56.                 ++nAlloy;
  57.                 a[nAlloy].c = x * 1000 + y;
  58.             }
  59.         }
  60.         nAlloy = 0;
  61.         FOR(i,1,n) FOR(j,1,n) {
  62.             int in; scanf("%d", &in);
  63.             if (i < j) {
  64.                 ++nAlloy;
  65.                 a[nAlloy].in = in;
  66.             }
  67.         }
  68.         nAlloy = 0;
  69.         FOR(i,1,n) FOR(j,1,n) {
  70.             int out; scanf("%d", &out);
  71.             if (i < j) {
  72.                 ++nAlloy;
  73.                 a[nAlloy].out = out;
  74.             }
  75.         }
  76.         sort(a+1, a+nAlloy+1);
  77.         // FOR(i,1,nAlloy) cout << a[i].c << ' ' << a[i].in << ' ' << a[i].out << endl;
  78.  
  79.         f[0][0][0] = 0;
  80.         FOR(i,0,nAlloy-1) FOR(j,0,i) FOR(t,0,1)
  81.             if (f[i][j][t] >= 0) {
  82.                 // Do not use
  83.                 if (t == 0) update(f[i+1][j][1], f[i][j][0]);
  84.                 // Use as out
  85.                 update(f[i+1][j+1][t], f[i][j][t] + a[i+1].out);
  86.                 // Use as in
  87.                 if (j > 0) update(f[i+1][j-1][t], f[i][j][t] + a[i+1].in);
  88.             }
  89.  
  90.         cout << nAlloy / 2 << ' ' << f[nAlloy][0][nAlloy % 2] << endl;
  91.     }
  92.     return 0;
  93. }
  94.  
  95.  
Success #stdin #stdout 0.01s 20904KB
comments (?)
stdin
copy 
3
0.000 0.012 0.312
0.012 0.000 0.111
0.312 0.111 0.000
0 3 5
3 0 4
5 4 0
0 4 9
4 0 5
9 5 0
stdout
copy 
1 8
https://ideone.com/U6Se0F
language:
C++14 (gcc 8.3)
created:
10 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!