oj.uz

Submission #720452

# Submission time Handle Problem Language Result Execution time Memory
720452 2023-04-08T10:15:50 Z Rafi22 Uplifting Excursion (BOI22_vault) C++14
0 / 100
 1 ms 340 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -