oj.uz

Submission #129741

# Submission time Handle Problem Language Result Execution time Memory
129741 2019-07-13T06:55:45 Z 임유진(#3141) 도장 모으기 (JOI14_stamps) C++14
85 / 100
 4 ms 380 KB 
#include <stdio.h>
#include <algorithm>

using namespace std;

#define MAXN 105

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]));
		for(int k = 1; k <= N - j; k++) gmin(dp[i][j], dp[i - 1][j + k] + (2 * j + 2 * k + 1) * T + k * (U[i] + E[i]));
		for(int k = 1; k <= j; k++) gmin(dp[i][j], dp[i - 1][j - k] + (2 * j - 2 * k + 1) * T + k * (V[i] + D[i]));
	}

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

Compilation message

stamps.cpp: In function 'int main()':
stamps.cpp:21: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:22: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 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 252 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 252 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 256 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 3 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 4 ms 376 KB Output is correct
9 Correct 4 ms 376 KB Output is correct
10 Correct 4 ms 376 KB Output is correct
11 Correct 4 ms 376 KB Output is correct
12 Correct 3 ms 376 KB Output is correct
13 Correct 4 ms 380 KB Output is correct
14 Correct 3 ms 376 KB Output is correct
15 Correct 3 ms 376 KB Output is correct
16 Correct 4 ms 376 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2 ms 376 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -