oj.uz

Submission #129835

# Submission time Handle Problem Language Result Execution time Memory
129835 2019-07-13T10:19:13 Z onjo0127 도장 모으기 (JOI14_stamps) C++11
100 / 100
 270 ms 212764 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 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 632 KB Output is correct
4 Correct 2 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 632 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 504 KB Output is correct
12 Correct 3 ms 504 KB Output is correct
13 Correct 2 ms 632 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 4 ms 1820 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 632 KB Output is correct
6 Correct 3 ms 1064 KB Output is correct
7 Correct 3 ms 1656 KB Output is correct
8 Correct 3 ms 1656 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 1784 KB Output is correct
12 Correct 3 ms 1784 KB Output is correct
13 Correct 3 ms 1784 KB Output is correct
14 Correct 3 ms 1784 KB Output is correct
15 Correct 4 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 250 ms 212216 KB Output is correct
2 Correct 1 ms 376 KB Output is correct
3 Correct 244 ms 212608 KB Output is correct
4 Correct 217 ms 187512 KB Output is correct
5 Correct 172 ms 155088 KB Output is correct
6 Correct 91 ms 72056 KB Output is correct
7 Correct 50 ms 45332 KB Output is correct
8 Correct 270 ms 212296 KB Output is correct
9 Correct 245 ms 212316 KB Output is correct
10 Correct 244 ms 212472 KB Output is correct
11 Correct 248 ms 212764 KB Output is correct
12 Correct 243 ms 212632 KB Output is correct
13 Correct 244 ms 212604 KB Output is correct
14 Correct 246 ms 212504 KB Output is correct
15 Correct 245 ms 212532 KB Output is correct
16 Correct 244 ms 212600 KB Output is correct
17 Correct 245 ms 212600 KB Output is correct