Submission #50799

#	Time	Username	Problem	Language	Result	Execution time	Memory
50799		waynetuinfor	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	477 ms	16932 KiB

sculpture

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

const int maxn = 2000 + 5;
long long s[maxn], y[maxn];
int dp[maxn][maxn], qu[maxn], dt[maxn];
vector<int> gr[maxn];

int main() {
    int n, a, b; scanf("%d %d %d", &n, &a, &b);
    for (int i = 1; i <= n; ++i) {
        scanf("%lld", &y[i]);
        s[i] = s[i - 1] + y[i];
    }
    if (a == 1) {
        long long ans = 0, mask = 0;
        for (int t = 44; t >= 0; --t) {
            for (int i = 0; i < maxn; ++i) gr[i].clear();
            for (int i = 1; i <= n; ++i) {
                for (int j = 0; j < i; ++j) {
                    if (mask & (s[i] - s[j])) continue;
                    int bit = (s[i] - s[j]) >> t & 1;
                    if (bit == 0) gr[j].push_back(i);
                }
            }
            memset(dt, -1, sizeof(dt));
            dt[0] = 0;
            int l = 0, r = 0;
            qu[r++] = 0;
            while (l < r) {
                int x = qu[l++];
                if (x == n) break;
                for (int u : gr[x]) if (dt[u] == -1) {
                    dt[u] = dt[x] + 1;
                    qu[r++] = u;
                }
            }
            if (dt[n] != -1 && dt[n] <= b) mask ^= (1ll << t);
            else ans ^= (1ll << t);
        }
        printf("%lld\n", ans);
        return 0;
    }
    long long ans = 0, mask = 0;
    for (int t = 44; t >= 0; --t) {
        for (int i = 0; i < maxn; ++i) for (int j = 0; j < maxn; ++j) dp[i][j] = maxn;
        dp[0][0] = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                for (int k = 0; k < j; ++k) {
                    if (mask & (s[j] - s[k])) continue;
                    int bit = (s[j] - s[k]) >> t & 1;
                    dp[j][i] = min(dp[j][i], dp[k][i - 1] | bit);
                }
            }
        }
        bool f = false;
        for (int i = a; i <= b; ++i) f |= dp[n][i] == 0;
        if (f) mask ^= (1ll << t);
        else ans ^= (1ll << t);
    }
    printf("%lld\n", ans);
    return 0;
}

Compilation message (stderr)

sculpture.cpp: In function 'int main()':
sculpture.cpp:10:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int n, a, b; scanf("%d %d %d", &n, &a, &b);
                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sculpture.cpp:12:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld", &y[i]);
         ~~~~~^~~~~~~~~~~~~~~

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