Submission #21944

# Submission time Handle Problem Language Result Execution time Memory
21944 2017-04-27T18:18:40 Z Hiasat Bali Sculptures (APIO15_sculpture) C++14
0 / 100
0 ms 2080 KB
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> plli;
typedef pair<double, double> pdd;
typedef pair<string, int> psi;

const int MOD = 1e9 + 7;
const int N = 100001;

const ll oo = 1e15;

typedef long long ll;

const int LOGN = 40;
int dp[110][110];

int n,a,b;
ll v[2010];

string ans = "";
bool check(int num ){
	for (int i = 0; i < ans.size(); ++i){
		if((((1ll << (LOGN - i - 1))&num)>0) != (ans[i]-'0')){
			return false;
		}
	}
	return ((num&(1ll << (LOGN - ans.size()-1))) == 0);
}
int can(int idx , int used){
	if(used > b)
		return 0;
	if(idx == n){
		return used >= a ? 1 : 0;
	}
	int &ret = dp[idx][used];
	if(ret != -1)
		return ret;
	ret = 0;
	ll sum = 0;
	for (int i = idx ; i < n; ++i){
		sum += v[i];

		if(check(sum)){

		ret = ret | can(i+1,used+1);
		}
	}
	return ret;
}
int main() {
 //	freopen("input.txt","r",stdin);
 	scanf("%d%d%d",&n,&a,&b);
 	for (int i = 0; i < n; ++i){
 		scanf("%lld",&v[i]);
 	}
 	while(ans.size() < LOGN){
 		memset(dp,-1,sizeof dp);
		if(can(0,0)){
			ans += '0';
		}else{
			ans += '1';
		}
 	}
 	ll sum = 0;
 	for (int i = 0; i < ans.size(); ++i){
 		sum += (1ll << (LOGN - i - 1)) * (ans[i]-'0');
 	}
 	cout << sum << endl;
	return 0;
}

Compilation message

sculpture.cpp: In function 'bool check(int)':
sculpture.cpp:27:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < ans.size(); ++i){
                    ^
sculpture.cpp: In function 'int main()':
sculpture.cpp:70:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < ans.size(); ++i){
                     ^
sculpture.cpp:57:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&n,&a,&b);
                           ^
sculpture.cpp:59:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%lld",&v[i]);
                       ^
# Verdict Execution time Memory Grader output
1 Correct 0 ms 2080 KB Output is correct
2 Incorrect 0 ms 2080 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 2080 KB Output is correct
2 Incorrect 0 ms 2080 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 2080 KB Output is correct
2 Incorrect 0 ms 2080 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 2080 KB Output is correct
2 Incorrect 0 ms 2080 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 2080 KB Output is correct
2 Incorrect 0 ms 2080 KB Output isn't correct
3 Halted 0 ms 0 KB -