Submission #43251

#	Time	Username	Problem	Language	Result	Execution time	Memory
43251		dqhungdl	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	299 ms	18500 KiB

sculpture

#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define ll long long
#define ii pair<int,int>
using namespace std;

const int N = 2e3 + 100;
int n,l,r;
int a[N];
int t = 0;
ll s = 1;
int f[2100][2100];
int q[N];
ll sum[N];

bool kt(int vt,int sl){
    if(vt == n+1) return (l <= sl) && (sl <= r);
    if(sl > r) return 0;
    if(f[vt][sl]) return 0;
    if(n > 100 && q[vt] < sl) return 0;
    f[vt][sl] = 1;
    ll x = 0;
    int ma = 0;
    for(int i = n; i >= vt; --i){
        x = sum[i] - sum[vt-1];
        if((x | s) == s)
            ma = kt(i+1,sl+1);
        if(ma) return 1;
    }
    q[vt] = sl;
    return 0;
}

main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    //freopen(".inp","r",stdin);
    //freopen(".out","w",stdout);
    cin >> n >> l >> r;
    for(int i = 1; i <= n; ++i)
        cin >> a[i],sum[i] = sum[i-1] +  a[i];
    s = (1LL << 41) - 1;
    t = 40;
    while(t >= 0){
        memset(f,0,sizeof(f));
        for(int i = 1; i <= n; ++i)
            q[i] = n+1;
        s -= (1LL << t);
        if(!kt(1,0))
            s += (1LL << t);
        --t;
    }
    cout << s;
}

Compilation message (stderr)

sculpture.cpp:36:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

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