oj.uz

Submission #5360

# Submission time Handle Problem Language Result Execution time Memory
5360 2014-04-09T16:02:56 Z model_code 도장 모으기 (JOI14_stamps) C++
100 / 100
 108 ms 36408 KB 
#include <cstdio>
#include <algorithm>
using namespace std;
const int INF = 1 << 30; // > 10^9

int U[3005], V[3005], D[3005], E[3005];
int dp[3005][3005];

int main() {
	int N, T;
	scanf("%d%d", &N, &T);
	for (int i = 1; i <= N; ++i) {
		scanf("%d%d%d%d", &U[i], &V[i], &D[i], &E[i]);
	}
	
	for (int i = 0; i <= N; ++i) fill(dp[i], dp[i] + N + 5, INF);
	dp[0][0] = 0;
	
	for (int i = 1; i <= N; ++i) {
		for(int j = 0; j < N + 5; ++j) {
			int base_cost = dp[i-1][j] + T * (j * 2 + 1);
			dp[i][j] = min(dp[i][j], base_cost + U[i] + V[i]);
			if (j > 0) dp[i][j] = min(dp[i][j], base_cost + D[i] + E[i]);
		}
		int best = INF;
		for(int j = 0; j < N + 5; ++j) {
			dp[i][j] = min(dp[i][j], best);
			best = min(best, dp[i-1][j] + T * (j * 2 + 1));
			best += V[i] + D[i];
			best = min(best, INF);
		}
		best = INF;
		for(int j = N + 4; j >= 0; --j) {
			dp[i][j] = min(dp[i][j], best);
			best = min(best, dp[i-1][j] + T * (j * 2 + 1));
			best += U[i] + E[i];
			best = min(best, INF);
		}
	}
	
	printf("%d\n", dp[N][0] + T);
	
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 36408 KB Output is correct
2 Correct 0 ms 36408 KB Output is correct
3 Correct 0 ms 36408 KB Output is correct
4 Correct 0 ms 36408 KB Output is correct
5 Correct 0 ms 36408 KB Output is correct
6 Correct 0 ms 36408 KB Output is correct
7 Correct 0 ms 36408 KB Output is correct
8 Correct 0 ms 36408 KB Output is correct
9 Correct 0 ms 36408 KB Output is correct
10 Correct 0 ms 36408 KB Output is correct
11 Correct 0 ms 36408 KB Output is correct
12 Correct 0 ms 36408 KB Output is correct
13 Correct 0 ms 36408 KB Output is correct

Subtask #2
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 36408 KB Output is correct
2 Correct 0 ms 36408 KB Output is correct
3 Correct 0 ms 36408 KB Output is correct
4 Correct 0 ms 36408 KB Output is correct
5 Correct 0 ms 36408 KB Output is correct
6 Correct 0 ms 36408 KB Output is correct
7 Correct 0 ms 36408 KB Output is correct
8 Correct 0 ms 36408 KB Output is correct
9 Correct 0 ms 36408 KB Output is correct
10 Correct 0 ms 36408 KB Output is correct
11 Correct 0 ms 36408 KB Output is correct
12 Correct 0 ms 36408 KB Output is correct
13 Correct 0 ms 36408 KB Output is correct
14 Correct 0 ms 36408 KB Output is correct
15 Correct 0 ms 36408 KB Output is correct
16 Correct 0 ms 36408 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 36408 KB Output is correct
2 Correct 0 ms 36408 KB Output is correct
3 Correct 96 ms 36408 KB Output is correct
4 Correct 84 ms 36408 KB Output is correct
5 Correct 60 ms 36408 KB Output is correct
6 Correct 28 ms 36408 KB Output is correct
7 Correct 12 ms 36408 KB Output is correct
8 Correct 96 ms 36408 KB Output is correct
9 Correct 100 ms 36408 KB Output is correct
10 Correct 92 ms 36408 KB Output is correct
11 Correct 92 ms 36408 KB Output is correct
12 Correct 92 ms 36408 KB Output is correct
13 Correct 92 ms 36408 KB Output is correct
14 Correct 100 ms 36408 KB Output is correct
15 Correct 108 ms 36408 KB Output is correct
16 Correct 100 ms 36408 KB Output is correct
17 Correct 100 ms 36408 KB Output is correct