Submission #168339

#	Time	Username	Problem	Language	Result	Execution time	Memory
168339		mat_v	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	223 ms	604 KiB

sculpture

#include <bits/stdc++.h>
#define maxn 2005
#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
using namespace std;
typedef long long ll;
const ll inf = 0x3f3f3f3f;
ll niz[maxn];
int n;
ll pref[maxn];
ll a,b;
ll mini;
bool bio[maxn][maxn];
bool dp[maxn][maxn];
int dp2[maxn];
bool check(ll broj){
    if(a > 1){
        dp[0][0] = 1;
        ff(i,1,n){
            dp[0][i] = dp[i][0] = 0;
        }
        ff(i,1,n){
            ff(j,1,n)dp[i][j] = 0;
        }
        ff(i,1,n){
            ff(j,1,b){
                ff(k,0,i - 1){
                    ll sta = pref[i] - pref[k];
                    if((sta | broj) == broj)dp[i][j] |= dp[k][j - 1];
                }
            }
        }
        ff(i,a,b){
            if(dp[n][i])return 1;
        }
        return 0;
    }else{
        dp2[0] = 0;
        ff(i,1,n){
            dp2[i] = 1e9;
            ff(j,0,i - 1){
                ll sta = pref[i] - pref[j];
                if((sta | broj) == broj)dp2[i] = min(dp2[i], dp2[j] + 1);
            }
        }
        return dp2[n] <= b;
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin >> n >> a >> b;
    for(int i=1; i<=n; i++)cin >> niz[i];
    pref[0] = 0;
    for(int i=1; i<=n; i++)pref[i] = pref[i - 1] + niz[i];
    ll st = (1LL<<62) - 1;
    for(int i=61; i>=0; i--){
        if(check(st - (1LL<<i)))st -= (1LL<<i);
    }
    cout << st << endl;
    return 0;
}
/*
8 1 4
1 2 1 1 1 0 4 6
*/

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