Submission #156064

#	Time	Username	Problem	Language	Result	Execution time	Memory
156064		HungAnhGoldIBO2020	도장 모으기 (JOI14_stamps)	C++14	100 / 100	334 ms	212244 KiB

stamps

#include<iostream>
using namespace std;
#define int long long
const int N=3e3+2;
const int inf=1e15+2;
int dp[N][N],u[N],v[N],d[N],e[N],min1[N][N],min2[N][N];
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,i,j,k,l,t;
	cin>>n>>t;
	for(i=1;i<=n;i++){
		cin>>u[i]>>v[i]>>d[i]>>e[i];
	}
	for(i=0;i<=n;i++){
		for(j=0;j<=n;j++){
			dp[i][j]=inf;
			if(i==0){
				min1[i][j]=0;
			}
			else{
				min1[i][j]=inf;
			}
			min2[i][j]=inf;
		}
	}
	dp[0][0]=0;
	for(i=1;i<=n;i++){
		for(j=0;j<=n;j++){
			if(j){
				dp[i][j]=min(dp[i][j],dp[i-1][j]+min(d[i]+e[i],u[i]+v[i])+2*j*t);
			}
			else{
				dp[i][j]=min(dp[i][j],dp[i-1][j]+u[i]+v[i]+2*j*t);
			}
		}
		for(j=0;j<=n;j++){
			if(j!=n){
				dp[i][j]=min(dp[i][j],min2[i-1][j+1]-j*(u[i]+e[i])+2*j*t);
			}
			if(j){
				dp[i][j]=min(dp[i][j],min1[i-1][j-1]+j*(d[i]+v[i])+2*j*t);
				min1[i][j]=min(min1[i][j-1],dp[i][j]-j*(d[i+1]+v[i+1]));
			}
			else{
				min1[i][j]=dp[i][j]-j*(d[i+1]+v[i+1]);
			}
		}
		for(j=n;j>=0;j--){
			if(j!=n){
				min2[i][j]=min(min2[i][j+1],dp[i][j]+j*(u[i+1]+e[i+1]));
			}
			else{
				min2[i][j]=dp[i][j]+j*(u[i+1]+e[i+1]);
			}
		}
//		for(j=0;j<=n;j++){
//			cout<<dp[i][j]<<' ';
//		}
//		cout<<endl;
	}
	cout<<dp[n][0]+t*(n+1);
}

Compilation message (stderr)

stamps.cpp: In function 'int main()':
stamps.cpp:10:12: warning: unused variable 'k' [-Wunused-variable]
  int n,i,j,k,l,t;
            ^
stamps.cpp:10:14: warning: unused variable 'l' [-Wunused-variable]
  int n,i,j,k,l,t;
              ^

• Subtask 1: 10 / 10
• Subtask 2: 75 / 75
• Subtask 3: 15 / 15