SHARE
TWEET

sgsg

a guest Apr 18th, 2019 104 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <fstream>
  3. #include <string.h>
  4. #include <limits.h>
  5.  
  6. #define NMAX 505
  7. #define XMAX 1001
  8.  
  9. using namespace std;
  10.  
  11. ifstream f("lenes.in");
  12. ofstream g("lenes.out");
  13.  
  14. int mini = XMAX, k, pos = 0, fr[XMAX], maxi;
  15. int p1 = 0, p2 = 0, p3 = 0, cost = 0;
  16.  
  17.  
  18. int cer, n, m, k1, k2, ans = INT_MAX, v[NMAX][NMAX];
  19. int i, j, c1, c2, sum;
  20.  
  21. void sorteaza(int);
  22. int lateral(int, int, int);
  23. int combina(int, int, int, int, int);
  24.  
  25. int main() {
  26.     freopen("lenes.in","r",stdin);
  27.     freopen("lenes.out","w",stdout);
  28.     /*FILE *f = fopen("lenes.in", "r");
  29.     FILE *g = fopen("lenes.out", "w");
  30.     f (stdin, "%d\n", &cer);
  31.     f (stdin, "%d %d %d %d\n", &n, &m, &k1, &k2);*/
  32.     cin >> cer;
  33.     cin >> n >> m >> k1 >> k2;
  34.     for(i = 1 ; i <= n ; ++i) {
  35.         for(j = 1 ; j <= m ; ++j) {
  36.             //f (stdin, "%d", v[i]+j);
  37.             cin >> v[i][j];
  38.             v[0][j] += v[i][j];
  39.         }
  40.         v[i][m + 1] = v[i][0] = XMAX;
  41.     }
  42.     if(cer == 1) {
  43.         for(j = 1 ; j <= m ; ++j) {
  44.             sum = v[0][j] + lateral(j - 1, j + 1, k1);
  45.             if(sum < ans) {
  46.                 ans = sum;
  47.                 //f  (stderr, "%d ", j);
  48.             }
  49.         }
  50.     }
  51.     else {
  52.         for(j = 1 ; j <= m ; ++j) {
  53.             sorteaza(j);
  54.             v[n + 1][j] = XMAX;
  55.         }
  56.         //debug matrice
  57.         /*for(i = 1 ; i <= n ; ++i) {
  58.             for(j = 1 ; j <= m ; ++j) {
  59.                 f  (stderr, "%02d ", v[i][j]);
  60.             }
  61.             f  (stderr, "\n");
  62.         }*/
  63.         for(c1 = 1 ; c1 < m - 1 ; ++c1)
  64.             for(c2 = c1 + 1 + (c1 == 1) ; c2 <= m ; ++c2) {
  65.                 sum = v[0][c1] + v[0][c2];
  66.                 if(c2 - c1 > 2) {
  67.                     sum += lateral(c1 - 1, c1 + 1, k1) + lateral(c2 - 1, c2 + 1, k2);
  68.                 }
  69.                 else if(c2 - c1 == 1) {
  70.                     sum += lateral(0, c1 - 1, k1) + lateral(0, c2 + 1, k2);
  71.                 }
  72.                 else {
  73.                     sum += combina(c1 - 1, c1 + 1, c2 + 1, k1, k2);
  74.                 }
  75.                 if(sum < ans) {
  76.                     ans = sum;
  77.                     //f  (stderr, "%d %d %d\n", c1, c2, sum);
  78.                     //cerr << c1 << ' ' << c2 << ' ' << sum << '\n';
  79.                 }
  80.                // if(c1 == 11 && c2 == 12)
  81.                     //cout << sum << '\n';
  82.  
  83.             }
  84.     }
  85.     //f  (stdout, "%d\n", ans);
  86.     cout << ans << '\n';
  87.     return 0;
  88. }
  89.  
  90. int lateral(int c1, int c2, int k) {
  91.     mini = XMAX, pos = 0, cost = 0;
  92.     memset(fr, 0, sizeof(fr));
  93.     for(i = 1 ; i <= n ; ++i) {
  94.         ++fr[v[i][c1]];
  95.         ++fr[v[i][c2]];
  96.         if(v[i][c1] < mini)
  97.             mini = v[i][c1];
  98.         if(v[i][c2] < mini)
  99.             mini = v[i][c2];
  100.     }
  101.     for(i = mini ; pos < k ; ++i) {
  102.         while(fr[i]-- && pos < k)
  103.             cost += i, ++pos;
  104.     }
  105.     return cost;
  106. }
  107. void sorteaza(int j) {
  108.     maxi = 0;
  109.     memset(fr, 0, sizeof(fr));
  110.     for(i = 1 ; i <= n ; ++i) {
  111.         fr[v[i][j]]++;
  112.         if(v[i][j] > maxi)
  113.             maxi = v[i][j];
  114.         if(v[i][j] < mini)
  115.             mini = v[i][j];
  116.     }
  117.     i = 0;
  118.     for(k = mini ; k <= maxi ; ++k)
  119.         while(fr[k]--)
  120.             v[++i][j] = k;
  121. }
  122.  
  123. int combina(int c1, int c2, int c3, int k1, int k2) {
  124.     p1 = 0, p2 = 0, p3 = 0, cost = 0;
  125.     while(k1 + k2 > p2) {
  126.         if(k1 == 0) {
  127.             if(v[p2 + 1][c2] <= v[p3 + 1][c3]) {
  128.                 ++p2;
  129.             }
  130.             else {
  131.                 ++p3;
  132.                 --k2;
  133.             }
  134.         }
  135.         else if(k2 == 0) {
  136.             if(v[p1 + 1][c1] <= v[p2 + 1][c3]) {
  137.                 ++p1;
  138.                 --k1;
  139.             }
  140.             else {
  141.                 ++p2;
  142.             }
  143.         }
  144.         else if(v[p1 + 1][c1] <= v[p2 + 1][c2] && v[p1 + 1][c1] <= v[p3 + 1][c3]) {
  145.             ++p1;
  146.             --k1;
  147.         }
  148.         else if(v[p2 + 1][c2] <= v[p1 + 1][c1] && v[p2 + 1][c2] <= v[p3 + 1][c3]) {
  149.             ++p2;
  150.         }
  151.         else {
  152.             ++p3;
  153.             --k2;
  154.         }
  155.     }
  156.     for(i = 1 ; i <= p1 ; ++i)
  157.         cost += v[i][c1];
  158.     for(i = 1 ; i <= p2 ; ++i)
  159.         cost += v[i][c2];
  160.     for(i = 1 ; i <= p3 ; ++i)
  161.         cost += v[i][c3];
  162.     return cost;
  163. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top