# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
129752 | 2019-07-13T07:20:19 Z | 이온조(#3139) | 도장 모으기 (JOI14_stamps) | C++14 | 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
# | 결과 | 실행 시간 | 메모리 | 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 |
# | 결과 | 실행 시간 | 메모리 | 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 |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 165 ms | 106232 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |