SHARE
TWEET

Swiss G

doofenshmirtzinc Oct 23rd, 2019 108 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef pair<int, int> pii;
  6.  
  7. const int S = 101;
  8. const int N = 34;
  9. pii dp[2][N][S][N][S];
  10.  
  11. inline void normalize(pii &p) {
  12.     if(p.first == 0) {
  13.         p.second = 1;
  14.         return ;
  15.     }
  16.     if(p.second == 0) {
  17.         p.first = 1;
  18.         return ;
  19.     }
  20.  
  21.     int sign = 0;
  22.     if(p.first > 0 != p.second > 0) {
  23.         sign = 1;
  24.     }
  25.     p.first = abs(p.first);
  26.     p.second = abs(p.second);
  27.     int g = __gcd(p.first, p.second);
  28.     p.first /= g, p.second /= g;
  29.  
  30.     if(sign) p.first *= -1;
  31. }
  32.  
  33. inline pii operator + (pii a, pii b) {
  34.     int dn = a.second * b.second;
  35.     int up = a.first * b.second + b.first * a.second;
  36.     pii ret(up, dn);
  37.     normalize(ret);
  38.     return ret;
  39. }
  40.  
  41. inline pii operator - (pii a, pii b) {
  42.     pii c = b;
  43.     c.first *= -1;
  44.     return a + c;
  45. }
  46.  
  47. inline bool operator < (pii &a, pii &b) {
  48.     return (a.first * b.second < a.second * b.first);
  49. }
  50.  
  51. int main() {
  52.     ios::sync_with_stdio(false);
  53.     cin.tie(0); cout.tie(0);
  54.  
  55.     int n, k;
  56.     cin >> n >> k;
  57.     vector<int> a(n);
  58.     for(int i=0; i<n; ++i) cin >> a[i];
  59.     int tot = accumulate(a.begin(), a.end(), 0);
  60.     vector<int> cum(n+1, 0);
  61.     for(int i=0; i<n; ++i) cum[i+1] = cum[i] + a[i];
  62.  
  63.     for(int c1=1; c1+2<=n; ++c1) {
  64.         for(int s1=c1; s1<=tot; ++s1) {
  65.             for(int c2=1; c2+1<=n-c1; ++c2) {
  66.                 for(int s2=c2; s2<=tot; ++s2) {
  67.                     int c3 = n - c1 - c2;
  68.                     int s3 = tot - s1 - s2;
  69.                     if(c3 <= 0 or s3 <= 0 or s1+s2+s3 >= S) {
  70.                         dp[n&1][c1][s1][c2][s2] = pii(S*S, 1);
  71.                         continue;
  72.                     }
  73.  
  74.                     pii p(s1, c1), q(s2, c2), r(s3, c3);
  75.                     pii avg = p + q + r;
  76.                     avg.second *= 3;
  77.                     normalize(avg);
  78.  
  79.                     dp[n&1][c1][s1][c2][s2] = avg;
  80.                     cerr << c1 << " " << s1 << " | " << c2 << " " << s2 << ": " << avg.first << "/" << avg.second << "\n";
  81.                 }
  82.             }
  83.         }
  84.     }
  85.  
  86.     pii mine(k, 1);
  87.     for(int i=n-1; i>=0; --i) {
  88.         for(int c1=0; c1+2<=i; ++c1) {
  89.             for(int s1=c1; s1<=cum[i]; ++s1) {
  90.                 for(int c2=0; c2+1<=i-c1; ++c2) {
  91.                     for(int s2=c2; s2<=cum[i]; ++s2) {
  92.                         int c3 = i - c1 - c2;
  93.                         int s3 = cum[i] - s1 - s2;
  94.                         if(c3 < 0 or s3 < 0) continue;
  95.  
  96.                         vector<pii> tempos;
  97.                         if(s1+a[i] <= tot) tempos.push_back(dp[(i&1)^1][c1+1][s1+a[i]][c2][s2]);
  98.                         if(s2+a[i] <= tot) tempos.push_back(dp[(i&1)^1][c1][s1][c2+1][s2+a[i]]);
  99.                         if(s3+a[i] <= tot) tempos.push_back(dp[(i&1)^1][c1][s1][c2][s2]);
  100.  
  101.                         if(tempos.empty()) {
  102.                             dp[n&1][c1][s1][c2][s2] = pii(S*S, 1);
  103.                             continue;
  104.                         }
  105.  
  106.                         pii best(S*S, 1), cur(S*S, 1);
  107.                         for(auto &qq : tempos) {
  108.                             auto temp = qq - mine;
  109.                             if(temp.first < 0) temp.first *= -1;
  110.                             if(temp < cur) best = qq, cur = temp;
  111.                             else if(temp == cur and qq < best) best = qq;
  112.                         }
  113.  
  114.                         dp[n&1][c1][s1][c2][s2] = best;
  115.                     }
  116.                 }
  117.             }
  118.         }
  119.     }
  120.  
  121.     auto res = dp[0][0][0][0][0];
  122.     normalize(res);
  123.     cout << res.first << "/" << res.second << "\n";
  124.  
  125.     return 0;
  126. }
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top