oj.uz

Submission #846458

# Submission time Handle Problem Language Result Execution time Memory
846458 2023-09-07T15:01:09 Z vjudge1 Bali Sculptures (APIO15_sculpture) C++17
37 / 100
 1 ms 600 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 600 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 1 ms 344 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 0 ms 344 KB Output is correct
24 Correct 0 ms 344 KB Output is correct
25 Correct 1 ms 344 KB Output is correct
26 Correct 1 ms 344 KB Output is correct
27 Correct 0 ms 344 KB Output is correct
28 Incorrect 0 ms 348 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1 ms 344 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 0 ms 344 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 0 ms 344 KB Output is correct
25 Correct 1 ms 504 KB Output is correct
26 Correct 1 ms 344 KB Output is correct
27 Correct 0 ms 344 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 1 ms 344 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 344 KB Output is correct
32 Correct 1 ms 344 KB Output is correct
33 Correct 1 ms 344 KB Output is correct
34 Correct 1 ms 348 KB Output is correct
35 Correct 1 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 0 ms 344 KB Output is correct
21 Correct 0 ms 344 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 344 KB Output is correct
24 Correct 0 ms 344 KB Output is correct
25 Correct 0 ms 344 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 344 KB Output is correct
28 Correct 1 ms 344 KB Output is correct
29 Correct 0 ms 344 KB Output is correct
30 Correct 1 ms 344 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 1 ms 348 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 1 ms 344 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 0 ms 344 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 344 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Incorrect 1 ms 344 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 500 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 600 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Incorrect 0 ms 344 KB Output isn't correct
16 Halted 0 ms 0 KB -