oj.uz

Submission #490820

# Submission time Handle Problem Language Result Execution time Memory
490820 2021-11-29T12:43:04 Z manizare Bali Sculptures (APIO15_sculpture) C++14
0 / 100
 1 ms 332 KB 
#include <bits/stdc++.h>
 
using namespace std;
#define IOS ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define pb push_back
#define all(a) a.begin(),a.end() 
typedef long long ll ;
const int maxn =1e6 + 10;
const int mod = 1e9 + 7 ;
const int maxq = 3000+10;
ll dp[110][110][110];
ll d[maxn];
ll pre[maxn];
 
int main()
{
	ll n , a , b ;
	cin >> n >> a >> b ;
	for(int i = 1; i <= n ; i++){
		cin >> d[i];
	}
	for(int i = 1 ; i<= n ; i++){
		pre[i] = pre[i-1] + d[i] ;
	}
	dp[1][1][n] = pre[n] ;
	
	ll answer = 1e18;
	if(a==1)answer = dp[1][1][n];
	for(int l = 1 ; l <= n ; l++){
		for(int r = l ; r <= n ; r++){
			dp[1][l][r] = pre[r] - pre[l-1];
			if(l==1 && r==n || l!=1 && r!=n)continue ;
			if(l==1){
				dp[2][l][r] = pre[r-1] | (pre[n]-pre[r-1]);
			}else{
				dp[2][l][r] = (pre[n]-pre[l]) | pre[l] ;
			}
			if(a==1 || a==2)
			answer = min(answer , dp[2][l][r]) ;
		}
	}
	for(int x = 3 ; x <= b ; x++){
		for(int l = 1 ; l <= n ; l++){
			for(int r = l ; r <= n ; r++){
				for(int s = 0 ; s <= x-1 ; s++){
					int f = x-1 ;
					if((l-1) < s || (n-r) < (f-s) || (s==0 && l!=1) || (f-s == 0 && r!=n))continue ;
					if(dp[x][l][r] == 0){
						dp[x][l][r] = dp[s][1][l-1] | (pre[r]-pre[l-1]) | dp[f-s][r+1][n] ;
					}else{
						dp[x][l][r] = min(dp[s][1][l-1] | (pre[r]-pre[l-1]) | dp[f-s][r+1][n] , dp[x][l][r]);
					}
				}
			//	cout << l << " " << r << " " << dp[x][l][r] << "<-\n";
			}
		}
	}
	for(int x = max(3ll,a) ; x <= b ; x++){
		for(int l = 1 ; l <= n ; l++){
			for(int r = l ; r <= n ; r ++){
				if(dp[x][l][r] == 0 || (x==1 && l!=1 && r!=n) || (x==2 && (l==1 && r==n || l!=1 && r!=n)))continue ;
				answer = min(answer , dp[x][l][r]);
			}
		}
	}
	cout << answer << "\n" ;
    return 0;
}
/*
6 1 3 
8 1 2 1 5 4
*/

Compilation message

sculpture.cpp: In function 'int main()':
sculpture.cpp:32:12: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   32 |    if(l==1 && r==n || l!=1 && r!=n)continue ;
      |       ~~~~~^~~~~~~
sculpture.cpp:61:69: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   61 |     if(dp[x][l][r] == 0 || (x==1 && l!=1 && r!=n) || (x==2 && (l==1 && r==n || l!=1 && r!=n)))continue ;
      |                                                                ~~~~~^~~~~~~

Subtask #1
0 / 9.0

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

Subtask #2
0 / 16.0

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

Subtask #3
0 / 21.0

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

Subtask #4
0 / 25.0

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

Subtask #5
0 / 29.0

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