Submission #673179

#TimeUsernameProblemLanguageResultExecution timeMemory
673179beedleBali Sculptures (APIO15_sculpture)C++17
71 / 100
52 ms468 KiB
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <set>
#include <iterator>
#include <stack>
#include <map>
#include <math.h>
#include <bitset>
#include <deque>
#include <string>
#include <tuple>
#include <queue>
#include <numeric>
#include <complex>
#include <assert.h>
#include <unordered_set>
#include <unordered_map>
#define ll long long
#define ld long long double
#define rep(i, a, b) for (long long i = a; i <= b; i++)
#define mod 1000000007ll
#define INF 1e18
#define pb push_back
#define ff first
#define ss second
#define endl '\n'
#define all(x) (x).begin (), (x).end ()
#define sz(x) (ll) (x).size ()
#define reunique(v) v.resize(std::unique(v.begin(), v.end()) - v.begin())
#define rank rnk
#define log lg
#define fast                                                                  \
    ios_base::sync_with_stdio (false);                                        \
    cin.tie (NULL);                                                           \
    cout.tie (NULL)
 
using namespace std;

signed main()
{
    fast;

    // freopen("curling.in","r",stdin);
    // freopen("curling.out","w",stdout);

    ll n,a,b;
    cin>>n>>a>>b;

    ll arr[n+1];
    rep(i,1,n)
    cin>>arr[i];

    ll s[n+1];
    s[0]=0;
    rep(i,1,n)
    s[i]=s[i-1]+arr[i];

    ll ans=0;

    for(ll idx=62;idx>=0;--idx)
    {
        ans+=(1ll<<idx)-1;
        
        vector<vector<int>> adj(n+1);
        rep(i,0,n)
        rep(j,i+1,n)
        if(((s[j]-s[i])&(~ans))==0)
        adj[i].pb(j);

        bool ok=false;
        if(n<=100)
        {
            vector <vector<bool>> ispath(n+1,vector<bool>(n+1));
            ispath[0][0]=true;

            rep(i,0,n)
            for(auto j:adj[i])
            rep(cnt,0,n)
            if(ispath[i][cnt])
            ispath[j][cnt+1]=true;

            rep(i,a,b)
            if(ispath[n][i])
            ok=true;
        }
        else
        {
            queue <ll> q;
            vector <ll> d(n+1,INF);
            q.push(0);
            d[0]=0;

            while(!q.empty())
            {
                auto v=q.front();
                q.pop();
                for(auto u:adj[v])
                if(d[u]!=INF)
                {
                    d[u]=1+d[v];
                    q.push(v);
                }
            }

            if(d[n]<=b)
            ok=true;
        }

        if(ok)
        ans-=(1ll<<idx)-1;
        else
        ans+=1;
    }

    cout<<ans;

    return 0;  
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...