Submission #846412

#	Time	Username	Problem	Language	Result	Execution time	Memory
846412		vjudge1	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	66 ms	600 KiB

sculpture

#include <bits/stdc++.h>
#define task ""
#define fi first
#define se second
#define pii pair<int, int>

using namespace std;
using ll = long long;

const ll mod = 998244353;
const int inf = 1e9 + 1;
const int arr = 100001;

int n, p, q, a[2001], dp[101][101], dp2[2001];
ll ps[2001];
void sub1(){
    ll finmask = 0;
    for(int x = 40; x >= 0; x--){
        memset(dp, 0, sizeof dp);
        dp[0][0] = 1;
        ll tmp = finmask | (1LL << x);
        for(int k = 1; k <= q; k++){
            for(int i = k; i <= n; i++){
                for(int j = k; j <= i; j++){
                    ll sum = ps[i] - ps[j - 1];
                    if(dp[j - 1][k - 1] && ((sum & tmp) == 0))dp[i][k] = 1;
                }
            }
        }
        for(int k = p; k <= q; k++){
            if(dp[n][k]){
                finmask |= (1LL << x);
                break;
            }
        }
    }
    ll res = 0;
    for(int i = 0; i <= 40; i++){
        if(!(finmask >> i & 1))res += (1LL << i);
    }
    cout << res << '\n'; 
}
void sub2(){
    ll finmask = 0;
    for(int x = 40; x >= 0; --x){
        memset(dp2, 0x3f, sizeof dp2);
        dp2[0] = 0;
        ll tmp = finmask | (1ll << x);
        for(int i = 1; i <= n; ++i)
        for(int j = i; j > 0; --j) {
            ll sum = ps[i] - ps[j - 1];
            if((sum & tmp) == 0)dp2[i] = min(dp2[i] , dp2[j - 1] + 1);
        }
        if(dp2[n] <= q)finmask = tmp;
    }
    ll res = 0;
    for(int i = 0 ; i <= 40 ; ++i)
    if((finmask >> i & 1) == 0) res |= (1ll << i);
    cout << res << '\n';
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    // freopen(task".inp" , "r" , stdin);  
    // freopen(task".out" , "w" , stdout);
    cin >> n >> p >> q;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        ps[i] = ps[i - 1] + a[i];
    }
    if(n <= 100)sub1();
    else sub2();
}

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