제출 #243134

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
243134		nicolaalexandra	Bali Sculptures (APIO15_sculpture)	C++14	71 / 100	1092 ms	27264 KiB

sculpture

#include <bits/stdc++.h>
#define DIM 2010
using namespace std;

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

int verif (long long mask, int bit){
    int i,j,k;
    for (i=1;i<=n;i++)
        L[i].clear();
    for (i=1;i<=n;i++){
        long long sum = 0;
        for (j=i;j<=n;j++){
            sum += v[j];

            int ok = 1;
            for (k=val;k>=bit;k--){
                if ( (((mask>>k)&1) == 0) &&  (((sum>>k)&1) == 1) ){
                    ok = 0;
                    break;
                }
            }

            if (ok)
                L[j].push_back(i);
        }

    }

    /// ok[i][j] - daca pot imparti primele i nr in j subsecv
    memset (ok,0,sizeof ok);
    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;
                    break;
                }}}}

    for (i=a;i<=b;i++)
        if (ok[n][i])
            return 1;

    return 0;
}

int main (){

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

    cin>>n>>a>>b;
    long long sum = 0;
    for (i=1;i<=n;i++){
        cin>>v[i];
        sum += v[i];
    }

    long long p = 1;
    val = 0;
    while (p * 2 <= sum){
        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;
}

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