Submission #720452

#	Time	Username	Problem	Language	Result	Execution time	Memory
720452		Rafi22	Uplifting Excursion (BOI22_vault)	C++14	0 / 100	1 ms	340 KiB

vault

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
ll mod=1000000007;
int inf=1000000007;
ll infl=1000000000000000007;

const int M=207;

ll a[2*M];
ll b[2*M];

ll DP[M*M*4];
ll nDP[M*M*4];

void gg()
{
    cout<<"impossible";
    exit(0);
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int m;
    ll l,sum=0,ans=0,act=0;
    cin>>m>>l;
    for(ll i=-m;i<=m;i++)
    {
        cin>>a[i+m];
        sum+=a[i+m]*i;
    }
    ans+=a[m];
    a[m]=0;
    if(sum>=l)
    {
        for(ll i=-m;i<=m;i++)
        {
            ll x;
            if(i<=0) x=a[i+m];
            else x=min(a[i+m],(l-act)/i);
            b[-i+m]+=x;
            a[i+m]-=x;
            ans+=x;
            act+=i*x;
        }
    }
    else
    {
        for(ll i=m;i>=-m;i--)
        {
            ll x;
            if(i>=0) x=a[i+m];
            else x=min(a[i+m],(l-act)/i);
            b[-i+m]+=x;
            a[i+m]-=x;
            ans+=x;
            act+=x*i;
        }
    }
    for(int i=-2*m*m;i<=2*m*m;i++) DP[i+2*m*m]=-infl;
    DP[2*m*m]=0;
    for(int i=1;i<=m;i++)
    {
        for(int j=-2*m*m;j<=2*m*m;j++) nDP[j+2*m*m]=-infl;
        for(int l=-2*m*m;l<-2*m*m+i;l++)
        {
            deque<pair<int,int>>Q;
            int c=0;
            for(int j=l;j<=2*m*m;j+=i)
            {
                c++;
                while(sz(Q)>0&&Q[0].nd<c-a[i+m]) Q.pop_front();
                while(sz(Q)>0&&Q.back().st<DP[j+2*m*m]-c) Q.pop_back();
                Q.pb({DP[j+2*m*m]-c,c});
                if(sz(Q)>0) nDP[j+2*m*m]=max(nDP[j+2*m*m],Q[0].st+c);
            }
            Q.clear();
            c=0;
            for(int j=l;j<=2*m*m;j+=i)
            {
                c++;
                while(sz(Q)>0&&Q[0].nd<c-a[i+m]-b[i+m]) Q.pop_front();
                if(c>a[i+m])
                {
                    while(sz(Q)>0&&Q.back().st<DP[j-a[i+m]*i+2*m*m]+c) Q.pop_back();
                    Q.pb({DP[j-a[i+m]*i+2*m*m]+c,c});
                }
                if(sz(Q)>0) nDP[j+2*m*m]=max(nDP[j+2*m*m],Q[0].st+a[i+m]-c);
            }
        }
        for(int j=-2*m*m;j<=2*m*m;j++) DP[j+2*m*m]=nDP[j+2*m*m];
    }
    for(int i=1;i<=m;i++)
    {
        for(int j=-2*m*m;j<=2*m*m;j++) nDP[j+2*m*m]=-infl;
        for(int l=2*m*m;l>2*m*m-i;l--)
        {
            deque<pair<int,int>>Q;
            int c=0;
            for(int j=l;j>=-2*m*m;j-=i)
            {
                c++;
                while(sz(Q)>0&&Q[0].nd<c-a[-i+m]) Q.pop_front();
                while(sz(Q)>0&&Q.back().st<DP[j+2*m*m]-c) Q.pop_back();
                Q.pb({DP[j+2*m*m]-c,c});
                if(sz(Q)>0) nDP[j+2*m*m]=max(nDP[j+2*m*m],Q[0].st+c);
            }
            Q.clear();
            c=0;
            for(int j=l;j>=-2*m*m;j-=i)
            {
                while(sz(Q)>0&&Q[0].nd<c-a[-i+m]-b[-i+m]) Q.pop_front();
                c++;
                if(c>a[-i+m])
                {
                    while(sz(Q)>0&&Q.back().st<DP[j+a[-i+m]*i+2*m*m]+c) Q.pop_back();
                    Q.pb({DP[j+a[-i+m]*i+2*m*m]+c,c});
                }
                if(sz(Q)>0) nDP[j+2*m*m]=max(nDP[j+2*m*m],Q[0].st+a[-i+m]-c);
            }
        }
        for(int j=-2*m*m;j<=2*m*m;j++) DP[j+2*m*m]=nDP[j+2*m*m];
    }
    l-=act;
    if(l<-2*m*m||l>2*m*m) gg();
    else
    {
        if(ans+DP[l+2*m*m]<0) gg();
        cout<<ans+(ll)DP[l+2*m*m];
    }

    return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 15
• Subtask 3-1: 0 / 10
• Subtask 3-2: 0 / 10
• Subtask 4-1: 0 / 10
• Subtask 4-2: 0 / 10
• Subtask 5-1: 0 / 10
• Subtask 5-2: 0 / 10
• Subtask 6-1: 0 / 10
• Subtask 6-2: 0 / 10