oj.uz

Submission #538137

# Submission time Handle Problem Language Result Execution time Memory
538137 2022-03-16T06:15:58 Z jamielim Kpart (eJOI21_kpart) C++14
100 / 100
 1620 ms 197192 KB 
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ii,ii> i4;
const int MOD=1000000007;
const int INF=1012345678;
const ll LLINF=1012345678012345678LL;
const double PI=3.1415926536;
const double EPS=1e-14;

int t;
int n;
int arr[1005];
int pref[1005];
int dp[1005][50005];
// the latest start point so that at end point i you have a subsequence of sum j

int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
			scanf("%d",&arr[i]);
			pref[i]=pref[i-1]+arr[i];
		}
		memset(dp,-1,sizeof(dp));
		for(int i=1;i<=n;i++){
			dp[i][0]=i;
			int m=min(pref[i],50005);
			if(pref[i]<50005)dp[i][pref[i]]=1;
			for(int j=1;j<m;j++){
				dp[i][j]=dp[i-1][j];
				if(j==arr[i])dp[i][j]=i;
				if(j>arr[i])dp[i][j]=max(dp[i][j],dp[i-1][j-arr[i]]);
			}
		}
		vector<int> ans;
		for(int i=2;i<=n;i++){
			bool poss=1;
			for(int j=1;j<=n-i+1;j++){
				int ttl=pref[j+i-1]-pref[j-1];
				if(ttl%2==1){poss=0;break;}
				if(dp[j+i-1][ttl/2]<j){poss=0;break;}
			}
			if(poss)ans.pb(i);
		}
		printf("%d ",SZ(ans));
		for(int i:ans)printf("%d ",i);
		printf("\n");
	}
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:27:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |  scanf("%d",&t);
      |  ~~~~~^~~~~~~~~
Main.cpp:29:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |   scanf("%d",&n);
      |   ~~~~~^~~~~~~~~
Main.cpp:31:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |    scanf("%d",&arr[i]);
      |    ~~~~~^~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 440 ms 196996 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 528 ms 196980 KB Output is correct
2 Correct 538 ms 196976 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 507 ms 196980 KB Output is correct
2 Correct 718 ms 197000 KB Output is correct
3 Correct 695 ms 196992 KB Output is correct
4 Correct 935 ms 197000 KB Output is correct
5 Correct 1266 ms 197128 KB Output is correct
6 Correct 1620 ms 197056 KB Output is correct
7 Correct 1443 ms 197192 KB Output is correct