Submission #1723694
Source Code Expand
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> P; typedef pair<int,P> P1; typedef pair<P,P> P2; typedef pair<double,int>Q; #define pu push #define pb push_back #define mp make_pair #define eps 1e-7 #define INF 1000000000 #define mod 1000000007 #define fi first #define sc second #define rep(i,x) for(int i=0;i<x;i++) #define repn(i,x) for(int i=1;i<=x;i++) #define SORT(x) sort(x.begin(),x.end()) #define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end()) #define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) #define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) bitset<22223*55>dp[2][56],dp2[2][56]; int n,m,k,a[56],b[56]; int hoge[22223*55],sum; int main(){ cin>>n>>m>>k; rep(i,n)cin>>a[i],sum+=a[i]; rep(i,m)cin>>b[i],sum+=b[i]; int cur=0,nxt=1; dp[0][0].set(0); rep(i,n){ rep(j,56) dp[nxt][j].reset(); for(int j=0;j<=i;j++){ dp[nxt][j] |= dp[cur][j]; dp[nxt][j+1] |= dp[cur][j]<<a[i]; } swap(cur,nxt); } int cur2=0,nxt2=1; dp2[0][0].set(0); rep(i,m){ rep(j,56) dp2[nxt2][j].reset(); for(int j=0;j<=i;j++){ dp2[nxt2][j] |= dp2[cur2][j]; dp2[nxt2][j+1] |= dp2[cur2][j]<<b[i]; } swap(cur2,nxt2); } //cout<<dp[cur][1][2]<<dp[cur][1][3]<<dp[cur][2][4]<<dp[cur][2][5]<<dp[cur][3][7]<<endl; ll ans = 0; for(int i=0;i<=min(min(m,n),k);i++){ if(k==1 && i==0) continue; int nxt = 0; for(int j=0;j<22223*55;j++){ if(dp[cur][n-i][j]) hoge[nxt++] = j; } //for(int i=0;i<nxt;i++) cout<<hoge[i]<<" "; int curr = sum/2; nxt--; for(int j=0;j<22223*55;j++){ if(dp2[cur2][i][j]){ //cout<<j<<endl; while(nxt>0 && hoge[nxt]>=curr-j) nxt--; //dp[cur][n-i][hoge-j] for(int f=max(0,nxt-2);f<nxt+2;f++){ ans = max(ans,1LL*(sum-hoge[nxt]-j)*(hoge[nxt]+j)); } } } } cout<<ans<<endl; }
Submission Info
Submission Time | |
---|---|
Task | D - DDPC特別ビュッフェ |
User | IH19980412 |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1894 Byte |
Status | WA |
Exec Time | 462 ms |
Memory | 35840 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | All | ||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 10 | 0 / 20 | 0 / 70 | ||||||||||||||
Status |
|
|
|
|
Set Name | Test Cases |
---|---|
Sample | 000_example_01.txt, 000_example_02.txt |
Subtask1 | 000_example_01.in, 010_rand_01.txt, 010_rand_02.txt, 010_rand_03.txt, 010_rand_04.txt, 010_rand_05.txt, 020_hand_01.txt, 020_hand_02.txt, 020_hand_03.txt, 020_hand_04.txt, 020_hand_05.txt, 020_hand_06.txt, 020_hand_07.txt, 030_max_01.txt, 030_max_02.txt, 030_max_03.txt, 030_max_04.txt, 030_max_05.txt |
Subtask2 | 000_example_01.txt, 000_example_02.txt, 020_hand_01.txt, 020_hand_03.txt, 020_hand_07.txt, 050_rand_01.txt, 050_rand_02.txt, 050_rand_03.txt, 060_rand_01.txt, 060_rand_02.txt, 060_rand_03.txt, 060_rand_04.txt, 060_rand_05.txt, 060_rand_06.txt, 060_rand_07.txt, 060_rand_08.txt, 060_rand_09.txt, 060_rand_10.txt, 070_rand_01.txt, 070_rand_02.txt, 070_rand_03.txt, 070_rand_04.txt, 070_rand_05.txt, 070_rand_06.txt, 070_rand_07.txt, 070_rand_08.txt, 070_rand_09.txt, 070_rand_10.txt, 080_hand_01.txt, 080_hand_02.txt, 080_hand_03.txt, 080_hand_04.txt, 080_hand_05.txt, 080_hand_06.txt, 080_hand_07.txt, 080_hand_08.txt, 080_hand_09.txt, 080_hand_10.txt, 080_hand_11.txt, 090_anti_greedy_01.txt, 090_anti_greedy_02.txt, 090_anti_greedy_03.txt, 090_anti_greedy_04.txt, 090_anti_greedy_05.txt, 090_anti_greedy_06.txt |
All | 000_example_01.txt, 000_example_02.txt, 010_rand_01.txt, 010_rand_02.txt, 010_rand_03.txt, 010_rand_04.txt, 010_rand_05.txt, 020_hand_01.txt, 020_hand_02.txt, 020_hand_03.txt, 020_hand_04.txt, 020_hand_05.txt, 020_hand_06.txt, 020_hand_07.txt, 030_max_01.txt, 030_max_02.txt, 030_max_03.txt, 030_max_04.txt, 030_max_05.txt, 050_rand_01.txt, 050_rand_02.txt, 050_rand_03.txt, 060_rand_01.txt, 060_rand_02.txt, 060_rand_03.txt, 060_rand_04.txt, 060_rand_05.txt, 060_rand_06.txt, 060_rand_07.txt, 060_rand_08.txt, 060_rand_09.txt, 060_rand_10.txt, 070_rand_01.txt, 070_rand_02.txt, 070_rand_03.txt, 070_rand_04.txt, 070_rand_05.txt, 070_rand_06.txt, 070_rand_07.txt, 070_rand_08.txt, 070_rand_09.txt, 070_rand_10.txt, 080_hand_01.txt, 080_hand_02.txt, 080_hand_03.txt, 080_hand_04.txt, 080_hand_05.txt, 080_hand_06.txt, 080_hand_07.txt, 080_hand_08.txt, 080_hand_09.txt, 080_hand_10.txt, 080_hand_11.txt, 090_anti_greedy_01.txt, 090_anti_greedy_02.txt, 090_anti_greedy_03.txt, 090_anti_greedy_04.txt, 090_anti_greedy_05.txt, 090_anti_greedy_06.txt, 100_rand_01.txt, 100_rand_02.txt, 100_rand_03.txt, 100_rand_04.txt, 100_rand_05.txt, 100_rand_06.txt, 100_rand_07.txt, 100_rand_08.txt, 100_rand_09.txt, 100_rand_10.txt, 110_rand_01.txt, 110_rand_02.txt, 110_rand_03.txt, 110_rand_04.txt, 110_rand_05.txt, 110_rand_06.txt, 110_rand_07.txt, 110_rand_08.txt, 110_rand_09.txt, 110_rand_10.txt, 120_max_01.txt, 120_max_02.txt, 120_max_03.txt, 120_max_04.txt, 120_max_05.txt, 130_max_01.txt, 130_max_02.txt, 130_max_03.txt, 130_max_04.txt, 130_max_05.txt, 140_hand_01.txt, 140_hand_02.txt, 140_hand_03.txt, 140_hand_04.txt, 140_hand_05.txt, 140_hand_06.txt, 140_hand_07.txt, 140_hand_08.txt, 140_hand_09.txt, 140_hand_10.txt, 140_hand_11.txt, 140_hand_12.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
000_example_01.txt | AC | 14 ms | 34688 KB |
000_example_02.txt | AC | 19 ms | 34688 KB |
010_rand_01.txt | AC | 167 ms | 34688 KB |
010_rand_02.txt | AC | 87 ms | 34688 KB |
010_rand_03.txt | AC | 22 ms | 34688 KB |
010_rand_04.txt | AC | 22 ms | 34688 KB |
010_rand_05.txt | AC | 172 ms | 34688 KB |
020_hand_01.txt | AC | 10 ms | 22400 KB |
020_hand_02.txt | AC | 14 ms | 34688 KB |
020_hand_03.txt | AC | 211 ms | 34688 KB |
020_hand_04.txt | AC | 286 ms | 34688 KB |
020_hand_05.txt | AC | 20 ms | 34688 KB |
020_hand_06.txt | WA | 20 ms | 34816 KB |
020_hand_07.txt | WA | 16 ms | 34688 KB |
030_max_01.txt | WA | 286 ms | 34688 KB |
030_max_02.txt | AC | 295 ms | 34688 KB |
030_max_03.txt | AC | 297 ms | 34688 KB |
030_max_04.txt | WA | 288 ms | 34688 KB |
030_max_05.txt | AC | 287 ms | 34688 KB |
050_rand_01.txt | WA | 228 ms | 34688 KB |
050_rand_02.txt | AC | 71 ms | 34688 KB |
050_rand_03.txt | AC | 219 ms | 34688 KB |
060_rand_01.txt | AC | 256 ms | 34688 KB |
060_rand_02.txt | AC | 80 ms | 34688 KB |
060_rand_03.txt | AC | 234 ms | 34688 KB |
060_rand_04.txt | AC | 208 ms | 34688 KB |
060_rand_05.txt | WA | 117 ms | 34688 KB |
060_rand_06.txt | AC | 186 ms | 34688 KB |
060_rand_07.txt | AC | 94 ms | 34688 KB |
060_rand_08.txt | AC | 165 ms | 34688 KB |
060_rand_09.txt | AC | 23 ms | 34688 KB |
060_rand_10.txt | WA | 81 ms | 34688 KB |
070_rand_01.txt | AC | 244 ms | 34688 KB |
070_rand_02.txt | AC | 137 ms | 34688 KB |
070_rand_03.txt | AC | 32 ms | 34688 KB |
070_rand_04.txt | WA | 39 ms | 34688 KB |
070_rand_05.txt | AC | 222 ms | 34688 KB |
070_rand_06.txt | AC | 95 ms | 34688 KB |
070_rand_07.txt | AC | 221 ms | 34688 KB |
070_rand_08.txt | AC | 105 ms | 34688 KB |
070_rand_09.txt | WA | 107 ms | 34688 KB |
070_rand_10.txt | AC | 34 ms | 34688 KB |
080_hand_01.txt | AC | 20 ms | 34688 KB |
080_hand_02.txt | AC | 21 ms | 34688 KB |
080_hand_03.txt | WA | 23 ms | 34688 KB |
080_hand_04.txt | AC | 218 ms | 34688 KB |
080_hand_05.txt | AC | 23 ms | 34688 KB |
080_hand_06.txt | AC | 54 ms | 34688 KB |
080_hand_07.txt | AC | 384 ms | 34688 KB |
080_hand_08.txt | AC | 421 ms | 34688 KB |
080_hand_09.txt | WA | 24 ms | 34688 KB |
080_hand_10.txt | AC | 24 ms | 34688 KB |
080_hand_11.txt | AC | 23 ms | 34688 KB |
090_anti_greedy_01.txt | WA | 384 ms | 34688 KB |
090_anti_greedy_02.txt | AC | 413 ms | 34688 KB |
090_anti_greedy_03.txt | AC | 407 ms | 34688 KB |
090_anti_greedy_04.txt | AC | 412 ms | 34688 KB |
090_anti_greedy_05.txt | AC | 409 ms | 34688 KB |
090_anti_greedy_06.txt | AC | 425 ms | 34688 KB |
100_rand_01.txt | AC | 272 ms | 35072 KB |
100_rand_02.txt | AC | 74 ms | 34688 KB |
100_rand_03.txt | AC | 237 ms | 35200 KB |
100_rand_04.txt | AC | 227 ms | 35072 KB |
100_rand_05.txt | WA | 119 ms | 34688 KB |
100_rand_06.txt | WA | 183 ms | 34688 KB |
100_rand_07.txt | AC | 98 ms | 34688 KB |
100_rand_08.txt | AC | 169 ms | 34688 KB |
100_rand_09.txt | WA | 23 ms | 34688 KB |
100_rand_10.txt | WA | 82 ms | 34816 KB |
110_rand_01.txt | AC | 320 ms | 35200 KB |
110_rand_02.txt | WA | 88 ms | 34944 KB |
110_rand_03.txt | AC | 301 ms | 35328 KB |
110_rand_04.txt | AC | 242 ms | 35072 KB |
110_rand_05.txt | AC | 162 ms | 34816 KB |
110_rand_06.txt | AC | 244 ms | 34944 KB |
110_rand_07.txt | AC | 100 ms | 34688 KB |
110_rand_08.txt | AC | 194 ms | 34688 KB |
110_rand_09.txt | WA | 22 ms | 34688 KB |
110_rand_10.txt | WA | 92 ms | 34944 KB |
120_max_01.txt | WA | 454 ms | 35328 KB |
120_max_02.txt | AC | 454 ms | 35328 KB |
120_max_03.txt | AC | 462 ms | 35328 KB |
120_max_04.txt | AC | 315 ms | 35200 KB |
120_max_05.txt | WA | 319 ms | 35072 KB |
130_max_01.txt | WA | 392 ms | 35840 KB |
130_max_02.txt | WA | 387 ms | 35712 KB |
130_max_03.txt | WA | 387 ms | 35840 KB |
130_max_04.txt | WA | 389 ms | 35840 KB |
130_max_05.txt | WA | 386 ms | 35584 KB |
140_hand_01.txt | AC | 420 ms | 34688 KB |
140_hand_02.txt | AC | 39 ms | 34688 KB |
140_hand_03.txt | WA | 428 ms | 34816 KB |
140_hand_04.txt | AC | 418 ms | 34816 KB |
140_hand_05.txt | AC | 20 ms | 34688 KB |
140_hand_06.txt | AC | 21 ms | 34688 KB |
140_hand_07.txt | AC | 416 ms | 34688 KB |
140_hand_08.txt | AC | 27 ms | 34688 KB |
140_hand_09.txt | AC | 54 ms | 34688 KB |
140_hand_10.txt | AC | 380 ms | 34688 KB |
140_hand_11.txt | AC | 224 ms | 34688 KB |
140_hand_12.txt | AC | 416 ms | 34688 KB |