oj.uz

Submission #243150

# Submission time Handle Problem Language Result Execution time Memory
243150 2020-06-30T12:40:51 Z nicolaalexandra Bali Sculptures (APIO15_sculpture) C++14
0 / 100
 5 ms 384 KB 
#include <bits/stdc++.h>
#define DIM 2010
using namespace std;

int v[DIM],dp2[DIM];
long long sp[DIM];
bitset <DIM> ok[DIM];
vector <int> L[DIM];
int n,a,b,val,i;

int verif (long long mask, int bit){
    int i,j,k;

    if (a == 1){

        for (i=1;i<=n;i++){
            dp2[i] = n+1;
            for (j=1;j<i;j++){
                long long sum = sp[i]-sp[j-1];
                if ( dp2[j-1] != n+1 && ( (~(mask>>bit)) & (sum>>bit) ) == 0)
                    dp2[i] = min (dp2[i],dp2[j-1]+1);
            }
        }

        return dp2[n] <= b;
    }


    for (i=1;i<=n;++i){
        L[i].clear();
        ok[i].reset();
    }

    for (i=1;i<=n;++i){
        long long sum = 0;
        for (j=i;j<=n;++j){
            sum += v[j];

            if ( ( (~(mask>>bit)) & (sum>>bit) ) == 0 )
                L[j].push_back(i);
        }

    }

    /// ok[i][j] - daca pot imparti primele i nr in j subsecv

    ok[0][0] = 1;
    for (i=1;i<=n;++i){
        for (j=1;j<=b;++j){
            for (auto poz : L[i]){
                if (ok[poz-1][j-1]){
                    ok[i][j] = 1;
                    if (i == n && j >= a && j <= b)
                        return 1;
                    break;
                }}}}

    return 0;
}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>a>>b;

    for (i=1;i<=n;++i){
        cin>>v[i];
        sp[i] = sp[i-1] + v[i];
    }

    long long p = 1;
    val = 0;
    while (p * 2 <= sp[n]){
        p *= 2;
        ++val;
    }

    long long mask = 0;
    for (int bit=val;bit>=0;--bit){
        if (!verif (mask,bit))
            mask += (1LL<<bit);
    }

    cout<<mask;



    return 0;
}

Compilation message

sculpture.cpp: In function 'int verif(long long int, int)':
sculpture.cpp:12:13: warning: unused variable 'k' [-Wunused-variable]
     int i,j,k;
             ^

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Incorrect 4 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Incorrect 5 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Incorrect 4 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Incorrect 5 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Incorrect 4 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -