oj.uz

Submission #130244

# Submission time Handle Problem Language Result Execution time Memory
130244 2019-07-14T11:35:17 Z HungAnhGoldIBO2020 Bali Sculptures (APIO15_sculpture) C++14
0 / 100
 2 ms 380 KB 
#include<iostream>
#define int long long
using namespace std;
const int N=2e3+4;
bool dp[N][N];
int sum[N][N],ar[N];
pair<int,int> range[N];
long long sum1[N];
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,i,j,k,a,b;
	long long temp=0,l;
	cin>>n>>a>>b;
	for(i=1;i<=n;i++){
		cin>>ar[i];
		sum1[i]=sum1[i-1]+ar[i];
	}
	dp[0][0]=true;
	for(i=1;i<=b;i++){
		sum[0][i]=1;
	}
	for(i=43;i>=0;i--){
		l=(1ll<<i);
		for(j=1;j<=n;j++){
			range[j].first=N-2;
			range[j].second=0;
			for(k=0;k<j;k++){
				if(((sum1[j]-sum1[k])|temp)-temp<l){
					range[j].first=min(range[j].first,k);
					range[j].second=max(range[j].second,k);
				}
			}
		}
		for(j=1;j<=n;j++){
			for(k=1;k<=min(j,b);k++){
				if(range[j].second>=range[j].first){
					l=sum[range[j].second][k-1];
					if(range[j].first){
						l-=sum[range[j].first-1][k-1];
					}
					if(l){
						dp[j][k]=true;
					}
					else{
						dp[j][k]=false;
					}
				}
				else{
					dp[j][k]=false;
				}
				sum[j][k]=sum[j-1][k]+dp[j][k];
				//cout<<j<<" "<<k<<' '<<dp[j][k]<<endl;
				if(j==n){
					if(k>=a&&dp[j][k]){
						break;
					}
					if(k==b){
						//cout<<i<<endl;
						temp|=(1ll<<i);
					}
				}
			}
		}
	}
	cout<<temp;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Incorrect 2 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Incorrect 2 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Incorrect 2 ms 380 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Incorrect 2 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Incorrect 2 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -