Submission #597248

#	Time	Username	Problem	Language	Result	Execution time	Memory
597248		Belphegor	Bali Sculptures (APIO15_sculpture)	C++14	9 / 100	265 ms	2516 KiB

sculpture

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,a,b;
ll arr[105];
ll subtask1(){
	ll ans = INT64_MAX;
	for(int i=1; i<(1<<n); i++){
		vector<int>v;
		for(int j=0; j<n; j++) if(i&(1<<j)) v.emplace_back(j);
		if(v.back()!=n-1) continue;
		if(v.size()<a || v.size()>b) continue;
		ll ret = 0;
		for(int j=0; j<=v[0]; j++) ret+=arr[j];
		for(int j=1; j<v.size(); j++){
			ll sum = 0;
			for(int k=v[j-1]+1; k<=v[j]; k++) sum+=arr[k];
			ret|=sum;
		}
		ans = min(ans,ret);
	}
	return ans;
}
int dp[55][22][1005];
int subtask2(){
	for(int i=n; i>=1; i--) arr[i] = arr[i-1];
	arr[0] = 0;
	for(int i=1; i<=n; i++) arr[i]+=arr[i-1];
	dp[0][0][0] = 1;
	int ret = arr[n];
	for(int i=0; i<=n; i++){
		for(int j=0; j<n; j++){
			for(int val = 0; val<=arr[n]; val++){
				if(!dp[i][j][val]) continue;
				for(int k=j+1; k<=n; k++){
					int v = val | (arr[k]-arr[j]);
					dp[i+1][k][v] = 1;
				}
			}
		}
		if(a<=i && i<=b){
			for(int j=0; j<=arr[n]; j++){
				if(dp[i][n][j]) ret = min(ret,j);
			}
		}
	}
	return ret;
}
int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin>>n>>a>>b;
	for(int i=0; i<n; i++) cin>>arr[i];
	if(n<=20) cout<<subtask1();
	else cout<<subtask2();
}

Compilation message (stderr)

sculpture.cpp: In function 'll subtask1()':
sculpture.cpp:12:14: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   12 |   if(v.size()<a || v.size()>b) continue;
      |      ~~~~~~~~^~
sculpture.cpp:12:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   12 |   if(v.size()<a || v.size()>b) continue;
      |                    ~~~~~~~~^~
sculpture.cpp:15:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |   for(int j=1; j<v.size(); j++){
      |                ~^~~~~~~~~

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