oj.uz

Submission #129753

# Submission time Handle Problem Language Result Execution time Memory
129753 2019-07-13T07:21:44 Z 이온조(#3139) 도장 모으기 (JOI14_stamps) C++14
100 / 100
 252 ms 212612 KB 
#include <bits/stdc++.h>
using namespace std;

const long long INF = 1LL * 1e18;
long long DP[3009][3009], L[3009][3009], R[3009][3009];
long long U[3009], V[3009], D[3009], E[3009];

int main() {
	int N, T; scanf("%d%d",&N,&T);
	for(int i=1; i<=N; i++) scanf("%lld%lld%lld%lld", &U[i], &V[i], &D[i], &E[i]);
	for(int i=1; i<=N; i++) DP[0][i] = INF;
	for(int i=1; i<=N; i++) {
		for(int j=0; j<=N; j++) {
			DP[i][j] = DP[i-1][j] + T + U[i] + V[i];
			if(j) DP[i][j] = min(DP[i][j], DP[i-1][j] + T + D[i] + E[i]);
		}
		L[i][0] = DP[i-1][0];
		for(int k=1; k<N; k++) L[i][k] = min(L[i][k-1], -(D[i] + V[i] - 2LL*T*i) * k + DP[i-1][k]);
		R[i][N] = (U[i] + E[i] + 2*T*i) * N + DP[i-1][N];
		for(int k=N-1; k>0; k--) R[i][k] = min(R[i][k+1], (U[i] + E[i] + 2LL*T*i) * k + DP[i-1][k]);

		for(int j=0; j<=N; j++) {
			if(j) DP[i][j] = min(DP[i][j], L[i][j-1] + T + (D[i] + V[i] - 2LL*T*i) * j);
			if(j+1<=N) DP[i][j] = min(DP[i][j], R[i][j+1] + T - (U[i] + E[i] + 2LL*T*i) * j);
		}
	}
	printf("%lld", DP[N][0] + T);
	return 0;
}

Compilation message

stamps.cpp: In function 'int main()':
stamps.cpp:9:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int N, T; scanf("%d%d",&N,&T);
            ~~~~~^~~~~~~~~~~~~~
stamps.cpp:10:31: 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 504 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 2 ms 632 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 2 ms 632 KB Output is correct
10 Correct 3 ms 632 KB Output is correct
11 Correct 2 ms 508 KB Output is correct
12 Correct 2 ms 504 KB Output is correct
13 Correct 2 ms 504 KB Output is correct

Subtask #2
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1656 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 1784 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 632 KB Output is correct
6 Correct 3 ms 1144 KB Output is correct
7 Correct 3 ms 1528 KB Output is correct
8 Correct 3 ms 1784 KB Output is correct
9 Correct 3 ms 1784 KB Output is correct
10 Correct 3 ms 1784 KB Output is correct
11 Correct 3 ms 1788 KB Output is correct
12 Correct 3 ms 1784 KB Output is correct
13 Correct 3 ms 1788 KB Output is correct
14 Correct 3 ms 1784 KB Output is correct
15 Correct 3 ms 1784 KB Output is correct
16 Correct 3 ms 1784 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 212248 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 246 ms 212600 KB Output is correct
4 Correct 210 ms 187424 KB Output is correct
5 Correct 171 ms 155012 KB Output is correct
6 Correct 79 ms 71956 KB Output is correct
7 Correct 49 ms 45176 KB Output is correct
8 Correct 252 ms 212412 KB Output is correct
9 Correct 249 ms 212452 KB Output is correct
10 Correct 246 ms 212396 KB Output is correct
11 Correct 247 ms 212472 KB Output is correct
12 Correct 249 ms 212508 KB Output is correct
13 Correct 247 ms 212472 KB Output is correct
14 Correct 251 ms 212600 KB Output is correct
15 Correct 247 ms 212612 KB Output is correct
16 Correct 245 ms 212572 KB Output is correct
17 Correct 249 ms 212452 KB Output is correct