Submission #21961

#	Time	Username	Problem	Language	Result	Execution time	Memory
21961		Hiasat	Bali Sculptures (APIO15_sculpture)	C++14	71 / 100	1000 ms	17816 KiB

sculpture

#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 ll oo = 1e15;

typedef long long ll;

const ll LOGN = 40;
int dp[2010][2010];

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

string ans = "";
bool check(ll num ){
	for (int i = 0; i < ans.size(); ++i){
		bool one = (((1ll << (LOGN - i - 1))&num)>0);
		if(one && (ans[i]-'0') == 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) && can(i+1,used+1)){
			ret = true;
			break;
		}
	}
	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 (stderr)

sculpture.cpp: In function 'bool check(ll)':
sculpture.cpp:26: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:69:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < ans.size(); ++i){
                     ^
sculpture.cpp:56: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:58:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%lld",&v[i]);
                       ^

• Subtask 1: 9 / 9
• Subtask 2: 16 / 16
• Subtask 3: 21 / 21
• Subtask 4: 25 / 25
• Subtask 5: 0 / 29