oj.uz

Submission #109840

# Submission time Handle Problem Language Result Execution time Memory
109840 2019-05-08T07:00:36 Z PeppaPig Bali Sculptures (APIO15_sculpture) C++14
0 / 100
 3 ms 384 KB 
#include <bits/stdc++.h>

#define long long long

using namespace std;

const int N = 2e3+5;

int n, A, B;
long pref[N];
bool C[N][N];

int main() {
    scanf("%d %d %d", &n, &A, &B);
    for(int i = 1; i <= n; i++) scanf("%lld", pref+i), pref[i] += pref[i-1];

    if(A == 1) {
        long ans = 0;
        for(int b = 62; ~b; b--) {
            int dp[N]; fill_n(dp, N, 1e9);
            dp[0] = 0;
            for(int i = 1; i <= n; i++) for(int j = i; j <= n; j++) {
                long sum = pref[j] - pref[i-1];
                if(!(sum >> b & 1) && ((sum | ans) >> (b + 1)) == (sum >> (b + 1)))
                    dp[j] = min(dp[j], dp[i-1] + 1);
            }
            if(dp[n] > B) ans |= 1ll << b;
        }
        printf("%lld\n", ans);
    } else {
        long l = 0, r = 1e13;
        while(l < r) {
            long mid = (l + r) >> 1;
            memset(C, false, sizeof C);
            C[0][0] = true;
            for(int k = 1; k <= n; k++) for(int i = 1; i <= n; i++) for(int j = i; j <= n; j++) {
                long sum = pref[j] - pref[i-1];
                if((sum & mid) == sum) C[j][k] |= C[i-1][k-1];
            }
            bool valid = false;
            for(int i = A; i <= B; i++) valid |= C[n][i];
            if(valid) r = mid;
            else l = mid + 1;
        }
        printf("%lld\n", r);
    }

    return 0;
}

Compilation message

sculpture.cpp: In function 'int main()':
sculpture.cpp:14:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &A, &B);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sculpture.cpp:15:54: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i <= n; i++) scanf("%lld", pref+i), pref[i] += pref[i-1];
                                 ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

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

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

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

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -