제출 #490820

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
490820		manizare	Bali Sculptures (APIO15_sculpture)	C++14	0 / 100	1 ms	332 KiB

sculpture

#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
*/

컴파일 시 표준 에러 (stderr) 메시지

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
• Subtask 2: 0 / 16
• Subtask 3: 0 / 21
• Subtask 4: 0 / 25
• Subtask 5: 0 / 29