# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
537446 | 2022-03-15T06:16:42 Z | jamezzz | Kpart (eJOI21_kpart) | C++17 | 586 ms | 28572 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]; int dp(int i,int v){ if(a[i]==v)return i; if(v<0||i==0)return 0; if(old[i][v]==t)return memo[i][v]; old[i][v]=t; 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 i=1;i<=n;++i){ for(int j=i;j<=n;++j){ if(die[j-i+1])continue; if((p[j]-p[i-1])%2==1)die[j-i+1]=true; if(dp(j,(p[j]-p[i-1])/2)<i)die[j-i+1]=true; } } 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 | 38 ms | 2856 KB | Output is correct |
2 | Correct | 145 ms | 7632 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 586 ms | 28572 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |