Submission #1111016

# Submission time Handle Problem Language Result Execution time Memory
1111016 2024-11-11T10:02:02 Z _rain_ Kpart (eJOI21_kpart) C++14
100 / 100
1328 ms 196484 KB
#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
#define name "main"
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define FORD(i,a,b) for(int i=(b);i>=(a);--i)

#define N 1'000
#define S 5'0000
int a[N+2],dp[N+2][S+2];
LL p[N+2]={};
int n;

void giai(){
	int n;scanf("%d",&n);
	FOR(i,1,n){
		scanf("%d",&a[i]);
		p[i]=p[i-1]+a[i];
	}
	int sum=p[n]/2;
	FOR(i,0,n) FOR(j,0,sum) dp[i][j]=0;
	FOR(i,1,n){
		FOR(j,0,sum) dp[i][j]=dp[i-1][j];
		if (a[i]<=sum) dp[i][a[i]]=i;
		FOR(j,a[i],sum){
			dp[i][j]=max(dp[i][j],dp[i-1][j-a[i]]);
		}
	}
	vector<int>pont;
	FOR(k,1,n){
		bool ok=true;
		FOR(j,1,n-k+1){
			LL x=p[j+k-1]-p[j-1];
			if (x%2==1||dp[j+k-1][x/2]<j){
				ok=false;
				break;
			}
		}
		if (ok) pont.push_back(k);
	}
	printf("%d ",pont.size());
	for(auto&x:pont) printf("%d ",x); printf("\n");
	return;
}

int32_t main(){
	int test;scanf("%d",&test);
	while(test--) giai();
	exit(0);
}

Compilation message

Main.cpp: In function 'void giai()':
Main.cpp:42:11: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
   42 |  printf("%d ",pont.size());
      |          ~^   ~~~~~~~~~~~
      |           |            |
      |           int          std::vector<int>::size_type {aka long unsigned int}
      |          %ld
Main.cpp:43:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   43 |  for(auto&x:pont) printf("%d ",x); printf("\n");
      |  ^~~
Main.cpp:43:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   43 |  for(auto&x:pont) printf("%d ",x); printf("\n");
      |                                    ^~~~~~
Main.cpp:16:13: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |  int n;scanf("%d",&n);
      |        ~~~~~^~~~~~~~~
Main.cpp:18:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |   scanf("%d",&a[i]);
      |   ~~~~~^~~~~~~~~~~~
Main.cpp: In function 'int32_t main()':
Main.cpp:48:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |  int test;scanf("%d",&test);
      |           ~~~~~^~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 2 ms 6480 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 6 ms 14672 KB Output is correct
2 Correct 17 ms 24912 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 64 ms 51812 KB Output is correct
2 Correct 170 ms 76364 KB Output is correct
3 Correct 220 ms 86600 KB Output is correct
4 Correct 375 ms 111384 KB Output is correct
5 Correct 898 ms 169544 KB Output is correct
6 Correct 1328 ms 193568 KB Output is correct
7 Correct 1163 ms 196484 KB Output is correct