# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
537450 | 2022-03-15T06:20:34 Z | jamezzz | Kpart (eJOI21_kpart) | C++17 | 2000 ms | 133416 KB |
#include <bits/stdc++.h> using namespace std; #define sf scanf #define pf printf int t,n,a[1005],p[1005],memo[1005][100005],old[1005][100005],die[1005]; inline int dp(int i,int v){ if(a[i]==v)return i; if(v<0||i==0)return 0; if(old[i][v]==t+1)return memo[i][v]; old[i][v]=t+1; return memo[i][v]=max(dp(i-1,v),dp(i-1,v-a[i])); } int main(){ sf("%d",&t); while(t--){ sf("%d",&n); for(int i=1;i<=n;++i)sf("%d",&a[i]),p[i]=a[i]+p[i-1]; memset(die,0,sizeof die); for(int k=1;k<=n;++k){ for(int i=1;i+k-1<=n;++i){ int j=i+k-1; if(die[k])break; if(((p[j]-p[i-1])&1)==1)die[k]=1; if(dp(j,(p[j]-p[i-1])/2)<i)die[k]=1; } } int cnt=0; for(int i=1;i<=n;++i)if(!die[i])++cnt; pf("%d ",cnt); for(int i=1;i<=n;++i)if(!die[i])pf("%d ",i); pf("\n"); } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 852 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 35 ms | 2912 KB | Output is correct |
2 | Correct | 116 ms | 7628 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 467 ms | 28448 KB | Output is correct |
2 | Correct | 1302 ms | 63380 KB | Output is correct |
3 | Correct | 1484 ms | 80400 KB | Output is correct |
4 | Execution timed out | 2095 ms | 133416 KB | Time limit exceeded |
5 | Halted | 0 ms | 0 KB | - |