fork download
  1. #include <bits/stdc++.h>
  2. #define pb push_back
  3. #define rep(i,n) for(int i = 0; i < n; i++)
  4. #define ll long long
  5.  
  6. using namespace std;
  7. int n,x,tot,ans1,ans2=11111111;
  8. int memo[100005][101];
  9. vector<int> v;
  10. int solve(int sum,int step,int chosen)
  11. {
  12. if(chosen==n/2) if(ans2-ans1>abs(abs(tot-2*sum))) { ans2=max(tot-sum,sum);ans1=min(tot-sum,sum); }
  13. if(sum>tot||step>=n) return 0;
  14.  
  15. if(memo[sum][step]!=-1) return memo[sum][step];
  16.  
  17. solve(sum+v[step],step+1,chosen+1);
  18. solve(sum,step+1,chosen);
  19. return memo[sum][step] = sum ;
  20. }
  21.  
  22. int main()
  23. {
  24. int tc;
  25. cin >> tc ;
  26. rep(qq,tc)
  27. {
  28. cin >> n ;
  29. v.clear();
  30. tot=0;
  31. rep(i,n)
  32. {
  33. cin >> x ;
  34. v.pb(x);
  35. tot+=x;
  36. }
  37.  
  38. memset(memo, -1, sizeof(memo));
  39. solve(0,0,0);
  40. cout << "Case " << qq+1 << ": " << ans1 << " " <<ans2 <<endl;
  41. }
  42. return 0;
  43. }
  44.  
Time limit exceeded #stdin #stdout 5s 42184KB
stdin
Standard input is empty
stdout
Case 1: 0 0
Case 2: 0 0
Case 3: 0 0
Case 4: 0 0
Case 5: 0 0
Case 6: 0 0
Case 7: 0 0
Case 8: 0 0
Case 9: 0 0
Case 10: 0 0
Case 11: 0 0
Case 12: 0 0
Case 13: 0 0
Case 14: 0 0
Case 15: 0 0
Case 16: 0 0
Case 17: 0 0
Case 18: 0 0
Case 19: 0 0
Case 20: 0 0
Case 21: 0 0
Case 22: 0 0
Case 23: 0 0
Case 24: 0 0
Case 25: 0 0
Case 26: 0 0
Case 27: 0 0
Case 28: 0 0
Case 29: 0 0
Case 30: 0 0
Case 31: 0 0
Case 32: 0 0
Case 33: 0 0
Case 34: 0 0
Case 35: 0 0
Case 36: 0 0
Case 37: 0 0
Case 38: 0 0
Case 39: 0 0
Case 40: 0 0
Case 41: 0 0
Case 42: 0 0
Case 43: 0 0
Case 44: 0 0
Case 45: 0 0
Case 46: 0 0
Case 47: 0 0
Case 48: 0 0
Case 49: 0 0
Case 50: 0 0
Case 51: 0 0
Case 52: 0 0
Case 53: 0 0
Case 54: 0 0
Case 55: 0 0
Case 56: 0 0
Case 57: 0 0
Case 58: 0 0
Case 59: 0 0
Case 60: 0 0
Case 61: 0 0
Case 62: 0 0
Case 63: 0 0
Case 64: 0 0
Case 65: 0 0
Case 66: 0 0
Case 67: 0 0
Case 68: 0 0
Case 69: 0 0
Case 70: 0 0
Case 71: 0 0
Case 72: 0 0
Case 73: 0 0
Case 74: 0 0
Case 75: 0 0
Case 76: 0 0
Case 77: 0 0
Case 78: 0 0
Case 79: 0 0
Case 80: 0 0
Case 81: 0 0
Case 82: 0 0
Case 83: 0 0
Case 84: 0 0
Case 85: 0 0
Case 86: 0 0
Case 87: 0 0
Case 88: 0 0
Case 89: 0 0
Case 90: 0 0
Case 91: 0 0
Case 92: 0 0
Case 93: 0 0
Case 94: 0 0
Case 95: 0 0
Case 96: 0 0
Case 97: 0 0
Case 98: 0 0
Case 99: 0 0
Case 100: 0 0
Case 101: 0 0
Case 102: 0 0
Case 103: 0 0
Case 104: 0 0
Case 105: 0 0
Case 106: 0 0
Case 107: 0 0
Case 108: 0 0
Case 109: 0 0
Case 110: 0 0
Case 111: 0 0
Case 112: 0 0
Case 113: 0 0
Case 114: 0 0
Case 115: 0 0
Case 116: 0 0
Case 117: 0 0
Case 118: 0 0
Case 119: 0 0
Case 120: 0 0
Case 121: 0 0
Case 122: 0 0
Case 123: 0 0
Case 124: 0 0
Case 125: 0 0
Case 126: 0 0
Case 127: 0 0
Case 128: 0 0
Case 129: 0 0
Case 130: 0 0
Case 131: 0 0
Case 132: 0 0
Case 133: 0 0
Case 134: 0 0
Case 135: 0 0
Case 136: 0 0
Case 137: 0 0
Case 138: 0 0
Case 139: 0 0
Case 140: 0 0
Case 141: 0 0
Case 142: 0 0
Case 143: 0 0
Case 144: 0 0
Case 145: 0 0
Case 146: 0 0
Case 147: 0 0
Case 148: 0 0
Case 149: 0 0
Case 150: 0 0
Case 151: 0 0
Case 152: 0 0
Case 153: 0 0
Case 154: 0 0
Case 155: 0 0
Case 156: 0 0
Case 157: 0 0
Case 158: 0 0
Case 159: 0 0
Case 160: 0 0
Case 161: 0 0
Case 162: 0 0
Case 163: 0 0
Case 164: 0 0
Case 165: 0 0
Case 166: 0 0
Case 167: 0 0
Case 168: 0 0
Case 169: 0 0
Case 170: 0 0
Case 171: 0 0
Case 172: 0 0
Case 173: 0 0
Case 174: 0 0
Case 175: 0 0
Case 176: 0 0
Case 177: 0 0
Case 178: 0 0
Case 179: 0 0
Case 180: 0 0
Case 181: 0 0
Case 182: 0 0
Case 183: 0 0
Case 184: 0 0
Case 185: 0 0
Case 186: 0 0
Case 187: 0 0
Case 188: 0 0
Case 189: 0 0
Case 190: 0 0
Case 191: 0 0
Case 192: 0 0
Case 193: 0 0
Case 194: 0 0
Case 195: 0 0
Case 196: 0 0
Case 197: 0 0
Case 198: 0 0
Case 199: 0 0
Case 200: 0 0
Case 201: 0 0
Case 202: 0 0
Case 203: 0 0
Case 204: 0 0
Case 205: 0 0
Case 206: 0 0
Case 207: 0 0
Case 208: 0 0
Case 209: 0 0
Case 210: 0 0
Case 211: 0 0
Case 212: 0 0
Case 213: 0 0
Case 214: 0 0
Case 215: 0 0
Case 216: 0 0
Case 217: 0 0
Case 218: 0 0
Case 219: 0 0
Case 220: 0 0
Case 221: 0 0
Case 222: 0 0
Case 223: 0 0
Case 224: 0 0
Case 225: 0 0
Case 226: 0 0
Case 227: 0 0
Case 228: 0 0
Case 229: 0 0
Case 230: 0 0
Case 231: 0 0
Case 232: 0 0
Case 233: 0 0
Case 234: 0 0
Case 235: 0 0
Case 236: 0 0
Case 237: 0 0
Case 238: 0 0
Case 239: 0 0
Case 240: 0 0
Case 241: 0 0
Case 242: 0 0
Case 243: 0 0
Case 244: 0 0
Case 245: 0 0
Case 246: 0 0
Case 247: 0 0
Case 248: 0 0
Case 249: 0 0
Case 250: 0 0
Case 251: 0 0
Case 252: 0 0
Case 253: 0 0
Case 254: 0 0
Case 255: 0 0
Case 256: 0 0
Case 257: 0 0
Case 258: 0 0
Case 259: 0 0
Case 260: 0 0
Case 261: 0 0
Case 262: 0 0
Case 263: 0 0
Case 264: 0 0
Case 265: 0 0
Case 266: 0 0
Case 267: 0 0
Case 268: 0 0
Case 269: 0 0
Case 270: 0 0
Case 271: 0 0
Case 272: 0 0
Case 273: 0 0
Case 274: 0 0
Case 275: 0 0
Case 276: 0 0
Case 277: 0 0
Case 278: 0 0
Case 279: 0 0
Case 280: 0 0
Case 281: 0 0
Case 282: 0 0
Case 283: 0 0
Case 284: 0 0
Case 285: 0 0
Case 286: 0 0
Case 287: 0 0
Case 288: 0 0
Case 289: 0 0
Case 290: 0 0
Case 291: 0 0
Case 292: 0 0
Case 293: 0 0
Case 294: 0 0
Case 295: 0 0
Case 296: 0 0
Case 297: 0 0
Case 298: 0 0
Case 299: 0 0
Case 300: 0 0
Case 301: 0 0
Case 302: 0 0
Case 303: 0 0
Case 304: 0 0
Case 305: 0 0
Case 306: 0 0
Case 307: 0 0
Case 308: 0 0
Case 309: 0 0
Case 310: 0 0
Case 311: 0 0
Case 312: 0 0
Case 313: 0 0
Case 314: 0 0
Case 315: 0 0
Case 316: 0 0
Case 317: 0 0
Case 318: 0 0
Case 319: 0 0
Case 320: 0 0
Case 321: 0 0
Case 322: 0 0
Case 323: 0 0
Case 324: 0 0
Case 325: 0 0
Case 326: 0 0
Case 327: 0 0
Case 328: 0 0
Case 329: 0 0
Case 330: 0 0
Case 331: 0 0
Case 332: 0 0
Case 333: 0 0
Case 334: 0 0
Case 335: 0 0
Case 336: 0 0
Case 337: 0 0
Case 338: 0 0
Case 339: 0 0
Case 340: 0 0
Case 341: 0 0
Case 342: 0 0
Case 343: 0 0
Case 344: 0 0
Case 345: 0 0
Case 346: 0 0
Case 347: 0 0
Case 348: 0 0
Case 349: 0 0
Case 350: 0 0
Case 351: 0 0
Case 352: 0 0
Case 353: 0 0
Case 354: 0 0
Case 355: 0 0
Case 356: 0 0
Case 357: 0 0
Case 358: 0 0
Case 359: 0 0
Case 360: 0 0
Case 361: 0 0
Case 362: 0 0
Case 363: 0 0
Case 364: 0 0
Case 365: 0 0
Case 366: 0 0
Case 367: 0 0
Case 368: 0 0
Case 369: 0 0
Case 370: 0 0
Case 371: 0 0
Case 372: 0 0
Case 373: 0 0
Case 374: 0 0
Case 375: 0 0
Case 376: 0 0
Case 377: 0 0
Case 378: 0 0
Case 379: 0 0
Case 380: 0 0
Case 381: 0 0
Case 382: 0 0
Case 383: 0 0
Case 384: 0 0
Case 385: 0 0
Case 386: 0 0
Case 387: 0 0
Case 388: 0 0
Case 389: 0 0
Case 390: 0 0
Case 391: 0 0
Case 392: 0 0
Case 393: 0 0
Case 394: 0 0
Case 395: 0 0
Case 396: 0 0
Case 397: 0 0
Case 398: 0 0
Case 399: 0 0