Submission #113658

#	Time	Username	Problem	Language	Result	Execution time	Memory
113658		Akashi	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	216 ms	512 KiB

sculpture

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

int n, a, b;
long long x[2005];

int d[2005];
bool dp[105][105];

inline bool check(long long mask){
    if(n <= 100){
        memset(dp, 0, sizeof(dp));
        ///can we divide first i elements into j groups
        dp[0][0] = 1;
        for(int i = 1; i <= n ; ++i){
            for(int j = 0; j < i ; ++j){
                for(int k = 1; k <= b ; ++k){
                    if(dp[j][k - 1] && (x[i] - x[j]) - ((x[i] - x[j]) & mask) == 0)
                        dp[i][k] = 1;
                }
            }
        }

        for(int k = a; k <= b ; ++k)
            if(dp[n][k]) return 1;
    }
    else{
        memset(d, 0x3f, sizeof(d));
        d[0] = 0;
        for(int i = 1; i <= n ; ++i){
            for(int j = 0; j < i ; ++j){
                if(x[i] - x[j] - ((x[i] - x[j]) & mask) == 0)
                    d[i] = min(d[j] + 1, d[i]);
            }
        }

        if(d[n] <= b) return 1;
    }

    return 0;
}

int main()
{
    scanf("%d%d%d", &n, &a, &b);

    for(int i = 1; i <= n ; ++i) scanf("%lld", &x[i]), x[i] += x[i - 1];

    long long Sol = (1LL << 63) - 1;

    for(long long bit = (1LL << 62); bit >= 1 ; bit >>= 1) if(check(Sol ^ bit)) Sol ^= bit;

    printf("%lld", Sol);

    return 0;
}

/*
    6 1 3
    8 1 2 1 5 4
*/

Compilation message (stderr)

sculpture.cpp: In function 'int main()':
sculpture.cpp:49:33: warning: integer overflow in expression [-Woverflow]
     long long Sol = (1LL << 63) - 1;
                     ~~~~~~~~~~~~^~~
sculpture.cpp:45: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:47: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", &x[i]), x[i] += x[i - 1];
                                  ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~

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