Submission #1161892

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161892		alexander707070	Potatoes and fertilizers (LMIO19_bulves)	C++20	20 / 100	910 ms	6728 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[2][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%2][f]=dp[1-i%2][f];

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

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

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

	return 0;
}

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