Submission #1161889

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161889		alexander707070	Potatoes and fertilizers (LMIO19_bulves)	C++20	0 / 100	952 ms	327680 KiB

bulves

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

const long long inf=1e16;

int n,a[MAXN],b[MAXN];
int pos[MAXN],m,sum,suma;

long long dp[3007][30007];

int main(){

	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i]>>b[i];

		for(int f=1;f<=b[i];f++){
			m++; pos[m]=i;
		}

		suma+=a[i];
	}

	dp[0][0]=0;
	for(int i=1;i<=suma;i++)dp[0][i]=inf;

	for(int i=1;i<=n;i++){
		sum+=a[i];

		for(int f=0;f<=suma;f++){

			long long curr=0;
			dp[i][f]=dp[i-1][f];

			for(int k=1;k<=min(a[i],f);k++){
				curr+=abs(i-pos[f-k+1]);

				dp[i][f]=min(dp[i][f],curr+dp[i-1][f-k]);
			}
		}
	}

	cout<<dp[n][m]<<"\n";

	return 0;
}

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