oj.uz

Submission #73945

# Submission time Handle Problem Language Result Execution time Memory
73945 2018-08-29T10:13:03 Z KLPP Bali Sculptures (APIO15_sculpture) C++14
0 / 100
 4 ms 876 KB 
#include<iostream>

using namespace std;
typedef long long int lld;
#define INF 1000000000000000
lld DP[3000][3000];
lld Y[3000];
lld acc[3000];
lld solve(int pos, int groups){
	if(DP[pos][groups]!=-1)return DP[pos][groups];
	DP[pos][groups]=INF;
	for(int j=0;j<pos;j++){
		DP[pos][groups]=min(DP[pos][groups],(solve(j,groups-1)|(acc[pos]-acc[j])));
	}
	return DP[pos][groups];
}
int main(){
	int n,a,b;
	cin>>n>>a>>b;
	for(int i=0;i<n;i++)cin>>Y[i];
	acc[0]=0;
	for(int i=0;i<n;i++)acc[i+1]=acc[i]+Y[i];
	for(int i=0;i<=n;i++){
		for(int j=0;j<=b;j++)DP[i][j]=-1;
	}
	for(int j=0;j<=b;j++)DP[0][j]=INF;
	for(int i=0;i<=n;i++)DP[i][0]=INF;
	DP[0][0]=0;
	lld ans=INF;
	/*for(int i=0;i<=n;i++){
		for(int j=0;j<=b;j++)cout<<solve(i,j)<<" ";
		cout<<endl;
	}*/
	for(int j=a;j<=b;j++){
		ans=min(ans,solve(n,j));
		//cout<<solve(n,j)<<endl;
	}
	cout<<ans<<endl;
	return 0;
}

Subtask #1
0 / 9.0

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

Subtask #2
0 / 16.0

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

Subtask #3
0 / 21.0

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

Subtask #4
0 / 25.0

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

Subtask #5
0 / 29.0

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