oj.uz

Submission #129748

# Submission time Handle Problem Language Result Execution time Memory
129748 2019-07-13T07:14:07 Z 임유진(#3141) 도장 모으기 (JOI14_stamps) C++14
100 / 100
 104 ms 71132 KB 
#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

#define MAXN 3005

typedef long long lint;

lint U[MAXN], V[MAXN], D[MAXN], E[MAXN];
lint dp[MAXN][MAXN];

void gmin(lint &a, lint b) { a = min(a, b); }

int main() {
	int N;
	lint T;

	//freopen("input.txt", "r", stdin);

	scanf("%d%lld", &N, &T);
	for(int i = 1; i <= N; i++) scanf("%lld%lld%lld%lld", U + i, V + i, D + i, E + i);

	dp[1][0] = U[1] + V[1];
	for(int j = 1; j <= N; j++) dp[1][j] = j * (V[1] + D[1]);
	for(int i = 2; i <= N; i++) {
		for(int j = 0; j <= N; j++) 
			dp[i][j] = dp[i - 1][j] + (j == 0 ? T + U[i] + V[i] : (2 * j + 1) * T + min(U[i] + V[i], E[i] + D[i]));
		lint mn = dp[i - 1][0];
		for(int j = 1; j <= N; j++) {
			gmin(dp[i][j], mn + T + j * (V[i] + D[i]));
			gmin(mn, dp[i - 1][j] + 2 * j * T - j * (V[i] + D[i]));
		}
		mn = dp[i - 1][N] + 2 * N * T + N * (U[i] + E[i]);
		for(int j = N - 1; j >= 0; j--) {
			gmin(dp[i][j], mn + T - j * (U[i] + E[i]));
			gmin(mn, dp[i - 1][j] + 2 * j * T + j * (U[i] + E[i]));
		}
	}

	printf("%lld", dp[N][0] + 2 * T);
	return 0;
}

Compilation message

stamps.cpp: In function 'int main()':
stamps.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%lld", &N, &T);
  ~~~~~^~~~~~~~~~~~~~~~~~
stamps.cpp:23:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i <= N; i++) scanf("%lld%lld%lld%lld", U + i, V + i, D + i, E + i);
                              ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
75.0 / 75.0

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

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 70912 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 104 ms 71132 KB Output is correct
4 Correct 86 ms 62684 KB Output is correct
5 Correct 70 ms 51928 KB Output is correct
6 Correct 33 ms 24312 KB Output is correct
7 Correct 21 ms 15352 KB Output is correct
8 Correct 102 ms 70960 KB Output is correct
9 Correct 102 ms 71032 KB Output is correct
10 Correct 103 ms 71068 KB Output is correct
11 Correct 102 ms 71032 KB Output is correct
12 Correct 102 ms 71032 KB Output is correct
13 Correct 103 ms 71032 KB Output is correct
14 Correct 103 ms 71004 KB Output is correct
15 Correct 102 ms 71032 KB Output is correct
16 Correct 102 ms 71004 KB Output is correct
17 Correct 103 ms 71012 KB Output is correct