oj.uz

Submission #243130

# Submission time Handle Problem Language Result Execution time Memory
243130 2020-06-30T12:02:25 Z nicolaalexandra Bali Sculptures (APIO15_sculpture) C++14
0 / 100
 22 ms 16256 KB 
#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) != ((sum>>k)&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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 16256 KB Output is correct
2 Incorrect 22 ms 16128 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 16256 KB Output is correct
2 Incorrect 20 ms 16128 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

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

Subtask #4
0 / 25.0

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

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 16128 KB Output is correct
2 Incorrect 20 ms 16256 KB Output isn't correct
3 Halted 0 ms 0 KB -