Submission #243150

#	Time	Username	Problem	Language	Result	Execution time	Memory
243150		nicolaalexandra	Bali Sculptures (APIO15_sculpture)	C++14	0 / 100	5 ms	384 KiB

sculpture

#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 (stderr)

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
• Subtask 2: 0 / 16
• Subtask 3: 0 / 21
• Subtask 4: 0 / 25
• Subtask 5: 0 / 29