Submission #1329260

#	Time	Username	Problem	Language	Result	Execution time	Memory
1329260		xiaoxuanzheng	Potatoes and fertilizers (LMIO19_bulves)	C++17	100 / 100	147 ms	12456 KiB

bulves

#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
using namespace std;

const int N=5e5+10,M=3e4+10;
int n,a[N],b[N];
LL ans,d[N];
// int f[2][M<<1],s;
priority_queue<LL>q;

signed main(){
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&a[i],&b[i]);
        d[i]=a[i]-b[i]+d[i-1];
    }
    for(int i=1;i<n;i++){
        if(d[i]<0)ans-=d[i],d[i]=0;
        ans+=d[i];
        q.push(d[i]);
        q.push(d[i]);
        q.pop();
    }
    while(q.size()){
        ans-=min(d[n],q.top());
        q.pop();
    }
    printf("%lld\n",ans);
    // assert(n<=3000&&s<=30000);
    // memset(f,0x3f,sizeof(f));
    // for(int i=M;i<=M+s;i++)f[i&1][i]=0;
    // for(int i=1;i<n;i++){
    //     for(int j=M-s;j<=M+s;j++){
    //         f[i&1][j]=min(f[i&1][j-1],abs(j-M)+f[i&1^1][min(M+s,max(M-s-1,j+d[i]))]);
    //         // printf("%d %d\n",j,f[i&1][j]);
    //         //k<=j+d
    //         //D>=0
    //     }
    //     // if(i==1)printf("%d\n",f[i&1][M]);
    // }
    // printf("%d\n",f[n&1^1][min(M+s,max(M-s-1,M+d[n]))]);

    return 0;
}

Compilation message (stderr)

bulves.cpp: In function 'int main()':
bulves.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
bulves.cpp:18:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |         scanf("%d%d",&a[i],&b[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 24 / 24
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 10 / 10
• Subtask 5: 36 / 36