Submission #105703

#	Time	Username	Problem	Language	Result	Execution time	Memory
105703		Pro_ktmr	도장 모으기 (JOI14_stamps)	C++14	100 / 100	630 ms	212648 KiB

stamps

#include"bits/stdc++.h"
using namespace std;
#define LL long long
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define PB push_back
#define MP make_pair
#define all(x) x.begin(),x.end()

int N;
LL T,U[3001],V[3001],D[3001],E[3001];

LL solve(int,int);
LL dp1[3001][3001];
LL wa1(int now, int ret){
	if(ret >= N) return (1LL)<<40;
	if(dp1[now][ret] != -1) return dp1[now][ret];
	return dp1[now][ret] = min(solve(now+1, ret+1), wa1(now,ret+1)) + D[now]+V[now] + T*2;
}
LL dp2[3001][3001];
LL wa2(int now, int ret){
	if(ret <= 0) return (1LL)<<40;
	if(dp2[now][ret] != -1) return dp2[now][ret];
	return dp2[now][ret] = min(solve(now+1, ret-1), wa2(now,ret-1)) + U[now]+E[now] - T*2;
}
LL dp[3001][3001];
LL solve(int now, int ret){
	if(now == 0) return dp[0][0] = solve(1, 0) + T;
	if(now == N+1){
		if(ret == 0) return 0;
		else return (1LL)<<40;
	}
	if(dp[now][ret] != -1) return dp[now][ret];
	LL re = LLONG_MAX;
	//上りの最中
	re = min(re, solve(now+1, ret) + U[now] + V[now] + T*ret*2 + T);
	//下りの最中
	if(ret > 0) re = min(re, solve(now+1, ret) + D[now] + E[now] + T*ret*2 + T);
	//後で返ってくる
	re = min(re, wa1(now, ret)+T*ret*2+T);
	//折り返す
	re = min(re, wa2(now, ret)+T*ret*2+T);
	return dp[now][ret] = re;
}

int main(){
	cin >> N >> T;
	for(int i=0; i<N; i++) cin >> U[i+1] >> V[i+1] >> D[i+1] >> E[i+1];
	for(int i=0; i<=N; i++){
		for(int j=0; j<=N; j++){
			dp[i][j] = -1;
			dp1[i][j] = -1;
			dp2[i][j] = -1;
		}
	}
	cout << solve(0, 0) << endl;

	return 0;
}

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