Submission #551389

#	Time	Username	Problem	Language	Result	Execution time	Memory
551389		ala2	Bali Sculptures (APIO15_sculpture)	C++14	46 / 100	75 ms	16076 KiB

sculpture

    #include <bits/stdc++.h>
    #define owo(i,a, b) for(int i=(a); i<(b); ++i)
    #define uwu(i,a, b) for(int i=(a)-1; i>=(b); --i)
    #define senpai push_back
    #define ttgl pair<int, int> 
    #define ayaya cout<<"debug"<<endl
     
    using namespace std;
    using ll = long long;
    using ld = long double;
    const ll MOD = 1e9+7;
    const int INF = 0x3f3f3f3f;
    const ll INFLL = 0x3f3f3f3f3f3f3f3f;
    vector<ll> arr;
    vector<ll> psum;
    int dp[2002][2002];
    int n, a, b;
    ll currbest = 0;
    bool solve(ll bit) {
        ll mx = currbest+(1LL<<bit);
        if(a==1) {
            owo(i, 0, n+1) {
                dp[0][i] = INF;
            }
            dp[0][0] = 0;
            owo(i, 0, n) {
                owo(j, 0, i+1) {
                    //cout<<currbest<<" "<<(psum[i+1]-psum[j])<<" "<<(currbest|(psum[i+1]-psum[j]))<<" "<<mx<<"\n";
                    if((currbest|(psum[i+1]-psum[j]))<mx) {
                        dp[0][i+1] = min(dp[0][i+1] , dp[0][j] + 1);
                    }
                }
            }
            return dp[0][n]>b;
            
        }else {
            owo(i, 0, 2002) {
                owo(j, 0, 2002) {
                    dp[i][j] = 0;
                }
            }
            dp[0][0] = 1;
            owo(i, 0, n) {
                owo(j, 0, i+1) {
                    if((currbest|(psum[i+1]-psum[j]))<mx) {
                        owo(k, 0, b) {
                            if(dp[j][k]) {
                                dp[i+1][k+1] = 1;
                            }
                        }
                    }
                }
            }
            for(int i=a; i<=b; ++i) {
                if(dp[n][i]) {
                    return false;
                }
            }
            return true;
        }
    }
    int main()
    {
        //freopen("filename.in", "r", stdin);
        //freopen("filename.out", "w", stdout);
        cin.tie(0)->sync_with_stdio(0);
        cin>>n>>a>>b;
        arr.resize(n);
        psum.resize(n+1);
        psum[0] = 0;
        owo(i, 0, n) {
            cin>>arr[i];
            psum[i+1] = psum[i] + arr[i];
        }
        for(ll i = 35; i>=0; --i) {
            if(solve(i)) {
                currbest+=(1LL<<i);
            }
        }
        cout<<currbest<<"\n";
        return 0;
    }

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