oj.uz

답안 #499823

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
499823 2021-12-29T15:49:32 Z luka1234 Bootfall (IZhO17_bootfall) C++14
13 / 100
 1000 ms 476 KB 
#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
using namespace std;
ll findmin(ll a[],ll n){
	ll sum=0;
	for(ll k=1;k<=n;k++){
		sum+=a[k];
	}
	bool dp[n+1][sum+1];
	for(ll k=0;k<=n;k++){
		dp[k][0]=1;
	}
	for(ll k=1;k<=sum;k++){
		dp[0][k]=0;
	}
	for(ll i=1;i<=n;i++){
		for(ll j=1;j<=sum;j++){
			dp[i][j]=dp[i-1][j];
			if(j>=a[i])
			   dp[i][j]|=dp[i-1][j-a[i]];
		}
	}
	ll diff=1e9;
	for(ll k=sum/2;k>=0;k--){
		if(dp[n][k]==1){
			diff=sum-k*2;
			break;
		}
	}
	return diff;
}
int main(){
	ll n;
	cin>>n;
	ll a[n+1];
	ll a1[n+2];
	ll a2[n+2];
	ll sum=0;
	for(ll k=1;k<=n;k++){
		cin>>a[k];
		a1[k]=a[k];
		a2[k]=a[k];
		sum+=a[k];
	}
	vector<ll> ans;
	for(ll k=1;k<=sum;k++){
		a1[n+1]=k;
		a2[n+1]=k;
		ll ind=0;
		for(ll i=1;i<=n+1;i++){
			a2[i]=0;
			ll diff=findmin(a2,n+1);
			a2[i]=a1[i];
			if(diff!=0){
				ind=1;
				break;
			}
		}
		if(ind==0)
		   ans.push_back(k);
	}
	cout<<ans.size()<<"\n";
	for(ll k=0;k<ans.size();k++)
	    cout<<ans[k]<<' ';
	return 0;
}

Compilation message

bootfall.cpp: In function 'int main()':
bootfall.cpp:65:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |  for(ll k=0;k<ans.size();k++)
      |             ~^~~~~~~~~~~

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 288 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 4 ms 204 KB Output is correct
5 Correct 40 ms 300 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 2 ms 296 KB Output is correct
8 Correct 89 ms 312 KB Output is correct
9 Correct 5 ms 204 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 288 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 4 ms 204 KB Output is correct
5 Correct 40 ms 300 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 2 ms 296 KB Output is correct
8 Correct 89 ms 312 KB Output is correct
9 Correct 5 ms 204 KB Output is correct
10 Correct 25 ms 316 KB Output is correct
11 Correct 41 ms 288 KB Output is correct
12 Correct 8 ms 204 KB Output is correct
13 Correct 5 ms 204 KB Output is correct
14 Correct 42 ms 304 KB Output is correct
15 Correct 37 ms 204 KB Output is correct
16 Correct 38 ms 300 KB Output is correct
17 Correct 11 ms 288 KB Output is correct
18 Correct 25 ms 292 KB Output is correct
19 Correct 17 ms 304 KB Output is correct
20 Correct 28 ms 316 KB Output is correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 288 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 4 ms 204 KB Output is correct
5 Correct 40 ms 300 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 2 ms 296 KB Output is correct
8 Correct 89 ms 312 KB Output is correct
9 Correct 5 ms 204 KB Output is correct
10 Correct 25 ms 316 KB Output is correct
11 Correct 41 ms 288 KB Output is correct
12 Correct 8 ms 204 KB Output is correct
13 Correct 5 ms 204 KB Output is correct
14 Correct 42 ms 304 KB Output is correct
15 Correct 37 ms 204 KB Output is correct
16 Correct 38 ms 300 KB Output is correct
17 Correct 11 ms 288 KB Output is correct
18 Correct 25 ms 292 KB Output is correct
19 Correct 17 ms 304 KB Output is correct
20 Correct 28 ms 316 KB Output is correct
21 Execution timed out 1084 ms 476 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 288 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 4 ms 204 KB Output is correct
5 Correct 40 ms 300 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 2 ms 296 KB Output is correct
8 Correct 89 ms 312 KB Output is correct
9 Correct 5 ms 204 KB Output is correct
10 Correct 25 ms 316 KB Output is correct
11 Correct 41 ms 288 KB Output is correct
12 Correct 8 ms 204 KB Output is correct
13 Correct 5 ms 204 KB Output is correct
14 Correct 42 ms 304 KB Output is correct
15 Correct 37 ms 204 KB Output is correct
16 Correct 38 ms 300 KB Output is correct
17 Correct 11 ms 288 KB Output is correct
18 Correct 25 ms 292 KB Output is correct
19 Correct 17 ms 304 KB Output is correct
20 Correct 28 ms 316 KB Output is correct
21 Execution timed out 1084 ms 476 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 288 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 4 ms 204 KB Output is correct
5 Correct 40 ms 300 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 2 ms 296 KB Output is correct
8 Correct 89 ms 312 KB Output is correct
9 Correct 5 ms 204 KB Output is correct
10 Correct 25 ms 316 KB Output is correct
11 Correct 41 ms 288 KB Output is correct
12 Correct 8 ms 204 KB Output is correct
13 Correct 5 ms 204 KB Output is correct
14 Correct 42 ms 304 KB Output is correct
15 Correct 37 ms 204 KB Output is correct
16 Correct 38 ms 300 KB Output is correct
17 Correct 11 ms 288 KB Output is correct
18 Correct 25 ms 292 KB Output is correct
19 Correct 17 ms 304 KB Output is correct
20 Correct 28 ms 316 KB Output is correct
21 Execution timed out 1084 ms 476 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 288 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 4 ms 204 KB Output is correct
5 Correct 40 ms 300 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 2 ms 296 KB Output is correct
8 Correct 89 ms 312 KB Output is correct
9 Correct 5 ms 204 KB Output is correct
10 Correct 25 ms 316 KB Output is correct
11 Correct 41 ms 288 KB Output is correct
12 Correct 8 ms 204 KB Output is correct
13 Correct 5 ms 204 KB Output is correct
14 Correct 42 ms 304 KB Output is correct
15 Correct 37 ms 204 KB Output is correct
16 Correct 38 ms 300 KB Output is correct
17 Correct 11 ms 288 KB Output is correct
18 Correct 25 ms 292 KB Output is correct
19 Correct 17 ms 304 KB Output is correct
20 Correct 28 ms 316 KB Output is correct
21 Execution timed out 1084 ms 476 KB Time limit exceeded
22 Halted 0 ms 0 KB -