Submission #1329233

#	Time	Username	Problem	Language	Result	Execution time	Memory
1329233		xiaoxuanzheng	Potatoes and fertilizers (LMIO19_bulves)	C++17	0 / 100	87 ms	1092 KiB

bulves

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

const int N=3e3+10,M=3e4+10;
int n,a[N],b[N],f[2][M<<1],s,d[N];

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]);
        s+=a[i];
        d[i]=a[i]-b[i];
    }
    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],j+d[i]<=M+s?abs(j-M)+f[i&1^1][j+d[i]]:(int)1e9);
            // 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][M+d[n]]);
    return 0;
}

Compilation message (stderr)

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

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