Submission #865173

#	Time	Username	Problem	Language	Result	Execution time	Memory
865173		jk410	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	58 ms	2700 KiB

sculpture

#include <iostream>
#define minn(a,b) a=min(a,b)
using namespace std;
typedef long long ll;
const int INF=10000;
const int MAX=40;
int N,A,B;
ll Y[2001];
bool DP[2001][2001];
int DP2[2001];
ll solve(){
    ll mask=0;
    for (int t=MAX; t>=0; t--){
        mask^=(1LL<<t);
        for (int i=1; i<=N; i++){
            for (int j=1; j<=i; j++){
                DP[i][j]=false;
                for (int k=0; k<i; k++)
                    DP[i][j]|=(DP[k][j-1]&!((Y[i]-Y[k])&mask));
            }
        }
        bool flag=true;
        for (int i=A; i<=B; i++){
            if (DP[N][i]){
                flag=false;
                break;
            }
        }
        if (flag)
            mask^=(1LL<<t);
    }
    return (((1LL<<MAX+1)-1)^mask);
}
ll solve2(){
    ll mask=0;
    for (int t=MAX; t>=0; t--){
        mask^=(1LL<<t);
        for (int i=1; i<=N; i++){
            DP2[i]=INF;
            for (int j=0; j<i; j++){
                if (!((Y[i]-Y[j])&mask))
                    minn(DP2[i],DP2[j]+1);
            }
        }
        if (DP2[N]>B)
            mask^=(1LL<<t);
    }
    return (((1LL<<MAX+1)-1)^mask);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    DP[0][0]=true;
    cin>>N>>A>>B;
    for (int i=1; i<=N; i++){
        cin>>Y[i];
        Y[i]+=Y[i-1];
    }
    cout<<(A==1?solve2():solve());
    return 0;
}

Compilation message (stderr)

sculpture.cpp: In function 'll solve()':
sculpture.cpp:32:23: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   32 |     return (((1LL<<MAX+1)-1)^mask);
      |                    ~~~^~
sculpture.cpp: In function 'll solve2()':
sculpture.cpp:48:23: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   48 |     return (((1LL<<MAX+1)-1)^mask);
      |                    ~~~^~

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