#include <bits/stdc++.h> #define pb push_back #define rep(i,n) for(int i = 0; i < n; i++) #define ll long long using namespace std; int n,x,tot,ans1,ans2=11111111; int memo[100005][101]; vector<int> v; int solve(int sum,int step,int chosen) { if(chosen==n/2) if(ans2-ans1>abs(abs(tot-2*sum))) { ans2=max(tot-sum,sum);ans1=min(tot-sum,sum); } if(sum>tot||step>=n) return 0; if(memo[sum][step]!=-1) return memo[sum][step]; solve(sum+v[step],step+1,chosen+1); solve(sum,step+1,chosen); return memo[sum][step] = sum ; } int main() { int tc; cin >> tc ; rep(qq,tc) { cin >> n ; v.clear(); tot=0; rep(i,n) { cin >> x ; v.pb(x); tot+=x; } memset(memo, -1, sizeof(memo)); solve(0,0,0); cout << "Case " << qq+1 << ": " << ans1 << " " <<ans2 <<endl; } return 0; }
Standard input is empty
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