Submission #846458

#	Time	Username	Problem	Language	Result	Execution time	Memory
846458		vjudge1	Bali Sculptures (APIO15_sculpture)	C++17	37 / 100	1 ms	600 KiB

sculpture

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define task "test1"
#define minpos(x, y) (a[x] <= a[y] ? (x) : (y))
#define pll pair<ll, ll>
#define pii pair<int, int>

using namespace std;

int const nmax = 2e3+3;
int const mod = 1e9+7;
int const LG = 20;
int const base=3;

void open_file()
{
    if(fopen(task".inp","r"))
    {
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
}

void fast()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

int n,p,q;
int a[nmax],sb1[101][101],sb2[nmax];
ll pre[nmax];

void sub1(){
    ll ans=0;
    for(int bit=31;bit>=0;bit--){
        memset(sb1,0,sizeof(sb1));
        sb1[0][0]=1;
        ll tmp=ans|(1ll<<bit);
        for(int ngan=1;ngan<=q;ngan++){
            for(int i=ngan;i<=n;i++){
                for(int j=1;j<=i;j++){
                    ll sum=pre[i]-pre[j-1];
                    sb1[i][ngan]|=(sb1[j-1][ngan-1] && ((sum&tmp)==0));
                }
            }
        }
        for(int i=p;i<=q;i++){
            if(sb1[n][i]){
                ans|=(1ll<<bit);
                break;
            }
        }
    }
    ll res=0;
    for(int i=0;i<=31;i++){
        if(!(ans>>i&1)) res|=(1ll<<i);
    }
    cout << res;
}

void sub2(){
    ll ans=0;
    for(int bit=31;bit>=0;bit--){
        memset(sb2,0x3f,sizeof(sb2));
        sb2[0]=0;
        ll tmp=ans|(1ll<<bit);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=i;j++){
                ll sum=pre[i]-pre[j-1];
                if(sb2[j-1]<1e9 && ((sum&tmp)==0)){
                    sb2[i]=min(sb2[i],sb2[j-1]+1);
                }
            }
        }
        if(sb2[n]<=q) ans=tmp;
    }
    ll res=0;
    for(int i=0;i<=31;i++){
        if(!(ans>>i&1)) res|=(1ll<<i);
    }
    cout << res;
}

void input()
{
   cin >> n >> p >> q;
   for(int i=1;i<=n;i++) cin >> a[i],pre[i]=pre[i-1]+a[i];
}

void NGU()
{
    if(p!=1) sub1();
    else sub2();
}

int main()
{
    open_file();
    fast();
    input();
    NGU();
}
/*
*/

Compilation message (stderr)

sculpture.cpp: In function 'void open_file()':
sculpture.cpp:21:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
sculpture.cpp:22:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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