Submission #580463

#	Time	Username	Problem	Language	Result	Execution time	Memory
580463		urd05	Uplifting Excursion (BOI22_vault)	C++17	20 / 100	3582 ms	8140 KiB

vault

#include <bits/stdc++.h>
using namespace std;

int m;
long long l;
int dp0[1000001];
int dp[1000001];
const int zero=500000;
long long arr[202];
typedef pair<int,int> P;

int main(void) {
    scanf("%d %lld",&m,&l);
    for(int i=1;i<=m*2+1;i++) {
        scanf("%lld",&arr[i]);
    }
    long long total=l;
    long long ret=0;
    for(int i=m+2;i<=m*2+1;i++) {
        long long use=total/(i-m-1);
        use=min(use,arr[i]);
        total-=1LL*use*(i-m-1);
        use=max(use-100,0LL);
        arr[i]-=use;
        l-=1LL*use*(i-m-1);
        ret+=use;
        if (arr[i]>100) {
            arr[i]=100;
        }
    }
    for(int i=0;i<=zero*2;i++) {
        dp0[i]=-1e7;
        dp[i]=-1e7;
    }
    if (l>zero||l<-zero) {
        printf("impossible");
        return 0;
    }
    dp[zero]=0;
    for(int i=1;i<=m*2+1;i++) {
        if (i==m+1){
            for(int j=0;j<=zero*2;j++) {
                dp[j]=dp[j]+arr[m+1];
            }
            continue;
        }
        int val=abs(i-m-1);
        if (i<m+1) {
            for(int j=zero*2;j>zero*2-val;j--) {
                deque<P> dq;
                for(int k=j;k>=0;k-=val) {
                    int now=dp[k]+k/val;
                    while (!dq.empty()&&dq.back().second>k+arr[i]*val) {
                        dq.pop_back();
                    }
                    while (!dq.empty()&&dq.front().first<=now) {
                        dq.pop_front();
                    }
                    dq.push_front(P(now,k));
                    dp0[k]=max(dp0[k],dq.back().first-k/val);
                }
            }
        }
        else {
            for(int j=0;j<val;j++) {
                deque<P> dq;
                for(int k=j;k<=zero*2;k+=val) {
                    int now=dp[k]-k/val;
                    while (!dq.empty()&&dq.back().second<k-arr[i]*val) {
                        dq.pop_back();
                    }
                    while (!dq.empty()&&dq.front().first<=now) {
                        dq.pop_front();
                    }
                    dq.push_front(P(now,k));
                    dp0[k]=max(dp0[k],dq.back().first+k/val);
                }
            }
        }
        for(int j=0;j<=zero*2;j++) {
            dp[j]=dp0[j];
            dp0[j]=-1e7;
        }
    }
    if (dp[zero+l]<0) {
        printf("impossible");
        return 0;
    }
    printf("%lld",ret+dp[zero+l]);
}

Compilation message (stderr)

vault.cpp: In function 'int main()':
vault.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     scanf("%d %lld",&m,&l);
      |     ~~~~~^~~~~~~~~~~~~~~~~
vault.cpp:15:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |         scanf("%lld",&arr[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 15 / 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