oj.uz

Submission #888384

# Submission time Handle Problem Language Result Execution time Memory
888384 2023-12-17T08:40:13 Z pcc Bootfall (IZhO17_bootfall) C++14
28 / 100
 553 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>

const int mxn = 510;
const int C = mxn*mxn;
int mod = 998244353;
int arr[mxn];
int dp[C];
int del[mxn][C];
int n;
int sum = 0;

inline ll mad(int a,int b){
	a += b;
	return a>=mod?a-mod:a;
}
inline ll mub(int a,int b){
	return mad(a,mod-b);
}

inline bool check(int now){
	if(sum&1)return false;
	if(!dp[sum>>1])return false;
	int tsum = sum+now;
	for(int i = 1;i<=n;i++){
		tsum -= arr[i];
		if(tsum&1)return false;
		if(tsum/2<now)return false;
		if(!del[i][tsum>>1])return false;
		tsum += arr[i];
	}
	return true;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
	dp[0] = 1;
	for(int i = 1;i<=n;i++){
		cin>>arr[i];
		sum += arr[i];
		for(int j = C-1;j>=arr[i];j--)dp[j] =mad(dp[j],dp[j-arr[i]]);
	}
	for(int i = 1;i<=n;i++){
		for(int j = 0;j<C;j++)del[i][j] = dp[j];
		for(int j = arr[i];j<C;j++)del[i][j] = mub(del[i][j],del[i][j-arr[i]]);
	}
	vector<int> ans;
	for(int i = 1;i<C;i++){
		if(check(i))ans.push_back(i);
	}

	vector<int> ans2;
	mod = 712271227;
	memset(dp,0,sizeof(dp));
	dp[0] = 1;
	for(int i = 1;i<=n;i++){
		for(int j = C-1;j>=arr[i];j--)dp[j] =mad(dp[j],dp[j-arr[i]]);
	}
	for(int i = 1;i<=n;i++){
		for(int j = 0;j<C;j++)del[i][j] = dp[j];
		for(int j = arr[i];j<C;j++)del[i][j] = mub(del[i][j],del[i][j-arr[i]]);
	}
	for(auto &i:ans){
		if(check(i))ans2.push_back(i);
	}
	swap(ans,ans2);
	ans2.clear();


	mod = 1e9+7;
	memset(dp,0,sizeof(dp));
	dp[0] = 1;
	for(int i = 1;i<=n;i++){
		for(int j = C-1;j>=arr[i];j--)dp[j] =mad(dp[j],dp[j-arr[i]]);
	}
	for(int i = 1;i<=n;i++){
		for(int j = 0;j<C;j++)del[i][j] = dp[j];
		for(int j = arr[i];j<C;j++)del[i][j] = mub(del[i][j],del[i][j-arr[i]]);
	}
	for(auto &i:ans){
		if(check(i))ans2.push_back(i);
	}
	swap(ans,ans2);
	ans2.clear();


	mod = 1e8+7;
	memset(dp,0,sizeof(dp));
	dp[0] = 1;
	for(int i = 1;i<=n;i++){
		for(int j = C-1;j>=arr[i];j--)dp[j] =mad(dp[j],dp[j-arr[i]]);
	}
	for(int i = 1;i<=n;i++){
		for(int j = 0;j<C;j++)del[i][j] = dp[j];
		for(int j = arr[i];j<C;j++)del[i][j] = mub(del[i][j],del[i][j-arr[i]]);
	}
	for(auto &i:ans){
		if(check(i))ans2.push_back(i);
	}
	swap(ans,ans2);
	ans2.clear();
	/*
	for(int i = 0;i<=10;i++)cout<<dp[i]<<' ';cout<<endl;
	cout<<sum<<endl;
	cout<<endl;
	for(int i = 1;i<=n;i++){
		for(int j = 0;j<=10;j++)cout<<del[i][j]<<' ';cout<<endl;
	}

   */

	cout<<ans.size()<<'\n';
	for(auto &i:ans)cout<<i<<' ';
	return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 9308 KB Output is correct
2 Correct 14 ms 11356 KB Output is correct
3 Correct 12 ms 7260 KB Output is correct
4 Correct 9 ms 9308 KB Output is correct
5 Correct 26 ms 17500 KB Output is correct
6 Correct 18 ms 13632 KB Output is correct
7 Correct 14 ms 11356 KB Output is correct
8 Correct 26 ms 17500 KB Output is correct
9 Correct 21 ms 15452 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 9308 KB Output is correct
2 Correct 14 ms 11356 KB Output is correct
3 Correct 12 ms 7260 KB Output is correct
4 Correct 9 ms 9308 KB Output is correct
5 Correct 26 ms 17500 KB Output is correct
6 Correct 18 ms 13632 KB Output is correct
7 Correct 14 ms 11356 KB Output is correct
8 Correct 26 ms 17500 KB Output is correct
9 Correct 21 ms 15452 KB Output is correct
10 Correct 65 ms 36188 KB Output is correct
11 Correct 76 ms 36188 KB Output is correct
12 Correct 67 ms 36184 KB Output is correct
13 Correct 70 ms 32092 KB Output is correct
14 Correct 64 ms 34136 KB Output is correct
15 Correct 72 ms 34140 KB Output is correct
16 Correct 79 ms 36188 KB Output is correct
17 Correct 43 ms 23852 KB Output is correct
18 Correct 55 ms 30040 KB Output is correct
19 Correct 61 ms 32092 KB Output is correct
20 Correct 65 ms 36188 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 9308 KB Output is correct
2 Correct 14 ms 11356 KB Output is correct
3 Correct 12 ms 7260 KB Output is correct
4 Correct 9 ms 9308 KB Output is correct
5 Correct 26 ms 17500 KB Output is correct
6 Correct 18 ms 13632 KB Output is correct
7 Correct 14 ms 11356 KB Output is correct
8 Correct 26 ms 17500 KB Output is correct
9 Correct 21 ms 15452 KB Output is correct
10 Correct 65 ms 36188 KB Output is correct
11 Correct 76 ms 36188 KB Output is correct
12 Correct 67 ms 36184 KB Output is correct
13 Correct 70 ms 32092 KB Output is correct
14 Correct 64 ms 34136 KB Output is correct
15 Correct 72 ms 34140 KB Output is correct
16 Correct 79 ms 36188 KB Output is correct
17 Correct 43 ms 23852 KB Output is correct
18 Correct 55 ms 30040 KB Output is correct
19 Correct 61 ms 32092 KB Output is correct
20 Correct 65 ms 36188 KB Output is correct
21 Correct 140 ms 70992 KB Output is correct
22 Correct 162 ms 81352 KB Output is correct
23 Correct 117 ms 56608 KB Output is correct
24 Correct 210 ms 101732 KB Output is correct
25 Correct 204 ms 101716 KB Output is correct
26 Correct 220 ms 108288 KB Output is correct
27 Correct 215 ms 108104 KB Output is correct
28 Correct 216 ms 108024 KB Output is correct
29 Correct 221 ms 108120 KB Output is correct
30 Correct 210 ms 107996 KB Output is correct
31 Correct 218 ms 108052 KB Output is correct
32 Correct 221 ms 108112 KB Output is correct
33 Correct 211 ms 107860 KB Output is correct
34 Correct 210 ms 108000 KB Output is correct
35 Correct 218 ms 108112 KB Output is correct
36 Correct 233 ms 107860 KB Output is correct

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 9308 KB Output is correct
2 Correct 14 ms 11356 KB Output is correct
3 Correct 12 ms 7260 KB Output is correct
4 Correct 9 ms 9308 KB Output is correct
5 Correct 26 ms 17500 KB Output is correct
6 Correct 18 ms 13632 KB Output is correct
7 Correct 14 ms 11356 KB Output is correct
8 Correct 26 ms 17500 KB Output is correct
9 Correct 21 ms 15452 KB Output is correct
10 Correct 65 ms 36188 KB Output is correct
11 Correct 76 ms 36188 KB Output is correct
12 Correct 67 ms 36184 KB Output is correct
13 Correct 70 ms 32092 KB Output is correct
14 Correct 64 ms 34136 KB Output is correct
15 Correct 72 ms 34140 KB Output is correct
16 Correct 79 ms 36188 KB Output is correct
17 Correct 43 ms 23852 KB Output is correct
18 Correct 55 ms 30040 KB Output is correct
19 Correct 61 ms 32092 KB Output is correct
20 Correct 65 ms 36188 KB Output is correct
21 Correct 140 ms 70992 KB Output is correct
22 Correct 162 ms 81352 KB Output is correct
23 Correct 117 ms 56608 KB Output is correct
24 Correct 210 ms 101732 KB Output is correct
25 Correct 204 ms 101716 KB Output is correct
26 Correct 220 ms 108288 KB Output is correct
27 Correct 215 ms 108104 KB Output is correct
28 Correct 216 ms 108024 KB Output is correct
29 Correct 221 ms 108120 KB Output is correct
30 Correct 210 ms 107996 KB Output is correct
31 Correct 218 ms 108052 KB Output is correct
32 Correct 221 ms 108112 KB Output is correct
33 Correct 211 ms 107860 KB Output is correct
34 Correct 210 ms 108000 KB Output is correct
35 Correct 218 ms 108112 KB Output is correct
36 Correct 233 ms 107860 KB Output is correct
37 Correct 480 ms 208748 KB Output is correct
38 Correct 437 ms 208700 KB Output is correct
39 Correct 553 ms 257816 KB Output is correct
40 Runtime error 155 ms 262144 KB Execution killed with signal 9
41 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 9308 KB Output is correct
2 Correct 14 ms 11356 KB Output is correct
3 Correct 12 ms 7260 KB Output is correct
4 Correct 9 ms 9308 KB Output is correct
5 Correct 26 ms 17500 KB Output is correct
6 Correct 18 ms 13632 KB Output is correct
7 Correct 14 ms 11356 KB Output is correct
8 Correct 26 ms 17500 KB Output is correct
9 Correct 21 ms 15452 KB Output is correct
10 Correct 65 ms 36188 KB Output is correct
11 Correct 76 ms 36188 KB Output is correct
12 Correct 67 ms 36184 KB Output is correct
13 Correct 70 ms 32092 KB Output is correct
14 Correct 64 ms 34136 KB Output is correct
15 Correct 72 ms 34140 KB Output is correct
16 Correct 79 ms 36188 KB Output is correct
17 Correct 43 ms 23852 KB Output is correct
18 Correct 55 ms 30040 KB Output is correct
19 Correct 61 ms 32092 KB Output is correct
20 Correct 65 ms 36188 KB Output is correct
21 Correct 140 ms 70992 KB Output is correct
22 Correct 162 ms 81352 KB Output is correct
23 Correct 117 ms 56608 KB Output is correct
24 Correct 210 ms 101732 KB Output is correct
25 Correct 204 ms 101716 KB Output is correct
26 Correct 220 ms 108288 KB Output is correct
27 Correct 215 ms 108104 KB Output is correct
28 Correct 216 ms 108024 KB Output is correct
29 Correct 221 ms 108120 KB Output is correct
30 Correct 210 ms 107996 KB Output is correct
31 Correct 218 ms 108052 KB Output is correct
32 Correct 221 ms 108112 KB Output is correct
33 Correct 211 ms 107860 KB Output is correct
34 Correct 210 ms 108000 KB Output is correct
35 Correct 218 ms 108112 KB Output is correct
36 Correct 233 ms 107860 KB Output is correct
37 Correct 480 ms 208748 KB Output is correct
38 Correct 437 ms 208700 KB Output is correct
39 Correct 553 ms 257816 KB Output is correct
40 Runtime error 155 ms 262144 KB Execution killed with signal 9
41 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 9308 KB Output is correct
2 Correct 14 ms 11356 KB Output is correct
3 Correct 12 ms 7260 KB Output is correct
4 Correct 9 ms 9308 KB Output is correct
5 Correct 26 ms 17500 KB Output is correct
6 Correct 18 ms 13632 KB Output is correct
7 Correct 14 ms 11356 KB Output is correct
8 Correct 26 ms 17500 KB Output is correct
9 Correct 21 ms 15452 KB Output is correct
10 Correct 65 ms 36188 KB Output is correct
11 Correct 76 ms 36188 KB Output is correct
12 Correct 67 ms 36184 KB Output is correct
13 Correct 70 ms 32092 KB Output is correct
14 Correct 64 ms 34136 KB Output is correct
15 Correct 72 ms 34140 KB Output is correct
16 Correct 79 ms 36188 KB Output is correct
17 Correct 43 ms 23852 KB Output is correct
18 Correct 55 ms 30040 KB Output is correct
19 Correct 61 ms 32092 KB Output is correct
20 Correct 65 ms 36188 KB Output is correct
21 Correct 140 ms 70992 KB Output is correct
22 Correct 162 ms 81352 KB Output is correct
23 Correct 117 ms 56608 KB Output is correct
24 Correct 210 ms 101732 KB Output is correct
25 Correct 204 ms 101716 KB Output is correct
26 Correct 220 ms 108288 KB Output is correct
27 Correct 215 ms 108104 KB Output is correct
28 Correct 216 ms 108024 KB Output is correct
29 Correct 221 ms 108120 KB Output is correct
30 Correct 210 ms 107996 KB Output is correct
31 Correct 218 ms 108052 KB Output is correct
32 Correct 221 ms 108112 KB Output is correct
33 Correct 211 ms 107860 KB Output is correct
34 Correct 210 ms 108000 KB Output is correct
35 Correct 218 ms 108112 KB Output is correct
36 Correct 233 ms 107860 KB Output is correct
37 Correct 480 ms 208748 KB Output is correct
38 Correct 437 ms 208700 KB Output is correct
39 Correct 553 ms 257816 KB Output is correct
40 Runtime error 155 ms 262144 KB Execution killed with signal 9
41 Halted 0 ms 0 KB -