# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
537454 |
2022-03-15T06:22:58 Z |
jamezzz |
Kpart (eJOI21_kpart) |
C++17 |
|
2000 ms |
133072 KB |
#include <bits/stdc++.h>
using namespace std;
#define sf scanf
#define pf printf
inline int rd(){
int x=0;
char ch=getchar_unlocked();
while(!(ch&16))ch=getchar();//keep reading while current character is whitespace
while(ch&16){//this will break when ‘\n’ or ‘ ‘ is encountered
x=(x<<3)+(x<<1)+(ch&15);
ch=getchar_unlocked();
}
return x;
}
int t,n,a[1005],p[1005],memo[1005][50005],old[1005][50005],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(){
t=rd();
while(t--){
n=rd();
for(int i=1;i<=n;++i)a[i]=rd(),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");
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
852 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
34 ms |
2876 KB |
Output is correct |
2 |
Correct |
111 ms |
7416 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
448 ms |
28364 KB |
Output is correct |
2 |
Correct |
1296 ms |
62924 KB |
Output is correct |
3 |
Correct |
1482 ms |
80092 KB |
Output is correct |
4 |
Execution timed out |
2101 ms |
133072 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |