Submission #3248348

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
long long int n,l,sum[20000][500],f[20000],A[20000][500],m=0,minn,ans=0,ti;
int main()
{
//	std::ios::sync_with_stdio(false);
//	freopen("fireworks.in","r",stdin);
//	freopen("fireworks.out","w",stdout);
    int a,b,c,d,e,ll;
    cin>>n>>l;
    for(a=1;a<=450;a++)A[0][a]=1000000;
    for(a=1;a<=n;a++)
    {
    	cin>>b>>c;f[b]++;sum[b][f[b]]=c;if(a==n)ti=b;ll=max(ll,c);
	}
//	for(a=1;a<=ti;a++)
//	{
//		for(b=1;b<=f[a];b++)cout<<sum[a][b]<<" ";cout<<endl;
//	}
	for(a=1;a<=ll;a++)
	{
		for(b=1;b<=ti;b++)
		{
		    //minn=1000000;
			d=0;
			for(c=1;c<=f[b];c++)d+=abs(a-sum[b][c]);
			A[a][b]=min(A[a-1][b],A[a][b-1]+d);
		}
	}
	cout<<A[ll][ti];
}

Submission Info

Judge Result