oj.uz

Submission #105703

# Submission time Handle Problem Language Result Execution time Memory
105703 2019-04-14T04:16:03 Z Pro_ktmr 도장 모으기 (JOI14_stamps) C++14
100 / 100
 630 ms 212648 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 640 KB Output is correct
6 Correct 2 ms 560 KB Output is correct
7 Correct 3 ms 512 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 3 ms 556 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 2 ms 556 KB Output is correct
13 Correct 2 ms 512 KB Output is correct

Subtask #2
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1664 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 5 ms 1792 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 640 KB Output is correct
6 Correct 3 ms 1152 KB Output is correct
7 Correct 5 ms 1664 KB Output is correct
8 Correct 4 ms 1792 KB Output is correct
9 Correct 4 ms 1792 KB Output is correct
10 Correct 5 ms 1792 KB Output is correct
11 Correct 5 ms 1792 KB Output is correct
12 Correct 5 ms 1792 KB Output is correct
13 Correct 4 ms 1792 KB Output is correct
14 Correct 4 ms 1792 KB Output is correct
15 Correct 26 ms 1804 KB Output is correct
16 Correct 4 ms 1792 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 528 ms 212264 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 516 ms 212648 KB Output is correct
4 Correct 427 ms 187520 KB Output is correct
5 Correct 327 ms 155584 KB Output is correct
6 Correct 170 ms 72412 KB Output is correct
7 Correct 81 ms 45440 KB Output is correct
8 Correct 503 ms 212332 KB Output is correct
9 Correct 536 ms 212496 KB Output is correct
10 Correct 630 ms 212468 KB Output is correct
11 Correct 489 ms 212472 KB Output is correct
12 Correct 589 ms 212600 KB Output is correct
13 Correct 478 ms 212600 KB Output is correct
14 Correct 530 ms 212516 KB Output is correct
15 Correct 539 ms 212600 KB Output is correct
16 Correct 533 ms 212500 KB Output is correct
17 Correct 570 ms 212504 KB Output is correct