oj.uz

Submission #129752

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

int DP[3009][3009], L[3009][3009], R[3009][3009];
int 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("%d%d%d%d", &U[i], &V[i], &D[i], &E[i]);
	for(int i=1; i<=N; i++) DP[0][i] = 2e9;
	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] - 2*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] + 2*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] - 2*T*i) * j);
			if(j+1<=N) DP[i][j] = min(DP[i][j], R[i][j+1] + T - (U[i] + E[i] + 2*T*i) * j);
		}
	}
	printf("%d", DP[N][0] + T);
	return 0;
}

Compilation message

stamps.cpp: In function 'int main()':
stamps.cpp:8: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:9: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("%d%d%d%d", &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 3 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 504 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Correct 2 ms 680 KB Output is correct
12 Correct 2 ms 500 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 1528 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 1656 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 760 KB Output is correct
6 Correct 3 ms 1016 KB Output is correct
7 Correct 3 ms 1528 KB Output is correct
8 Correct 3 ms 1656 KB Output is correct
9 Correct 3 ms 1656 KB Output is correct
10 Correct 3 ms 1576 KB Output is correct
11 Correct 3 ms 1656 KB Output is correct
12 Correct 3 ms 1656 KB Output is correct
13 Correct 3 ms 1656 KB Output is correct
14 Correct 3 ms 1656 KB Output is correct
15 Correct 3 ms 1656 KB Output is correct
16 Correct 3 ms 1656 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 165 ms 106232 KB Output isn't correct
2 Halted 0 ms 0 KB -