oj.uz

답안 #48317

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
48317 2018-05-11T17:00:23 Z choikiwon 도장 모으기 (JOI14_stamps) C++17
100 / 100
 152 ms 1896 KB 
#include<bits/stdc++.h>
using namespace std;

const int MN = 3010;

int N, T;
int U[MN], V[MN], D[MN], E[MN];
int dp[2][MN][2][2];

int main() {
    scanf("%d %d", &N, &T);

    for(int i = 0; i < N; i++) {
        scanf("%d %d %d %d", &U[i], &V[i], &D[i], &E[i]);
    }

    for(int i = 1; i <= N; i++) dp[N & 1][i][1][0] = 1e9;
    for(int i = N - 1; i >= 0; i--) {
        for(int t = 0; t < 2; t++) {
            if(t) {
                for(int open = N; open >= 0; open--) {
                    for(int d = 0; d < 2; d++) {
                        dp[i & 1][open][t][d] = 1e9;
                        if(open < N) dp[i & 1][open][t][d] = min(dp[i & 1][open][t][d], dp[i & 1][open + 1][1][d | 1] + V[i] + D[i]);
                        dp[i & 1][open][t][d] = min(dp[i & 1][open][t][d], dp[i & 1][open][0][d]);
                    }
                }
            }
            else {
                for(int open = 0; open <= N; open++) {
                    for(int d = 0; d < 2; d++) {
                        dp[i & 1][open][t][d] = 1e9;
                        if(open) dp[i & 1][open][t][d] = min(dp[i & 1][open][t][d], dp[i & 1][open - 1][0][d | 1] + U[i] + E[i]);
                        if(d) dp[i & 1][open][t][d] = min(dp[i & 1][open][t][d], dp[ (i ^ 1) & 1 ][open][1][0] + T * (2 * open + 1));
                        else {
                            int cost = U[i] + V[i];
                            if(open) cost = min(cost, D[i] + E[i]);
                            dp[i & 1][open][t][d] = min(dp[i & 1][open][t][d], dp[ (i ^ 1) & 1 ][open][1][0] + cost + T * (2 * open + 1));
                        }
                    }
                }
            }
        }
    }

    for(int i = N - 1; i >= 0; i--) {
        for(int open = 0; open <= N; open++) {
            for(int t = 0; t < 2; t++) {
                for(int d = 0; d < 2; d++) {

                }
            }
        }
    }

    printf("%d", T + dp[0][0][1][0]);
}

Compilation message

stamps.cpp: In function 'int main()':
stamps.cpp:11:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &N, &T);
     ~~~~~^~~~~~~~~~~~~~~~~
stamps.cpp:14:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d %d", &U[i], &V[i], &D[i], &E[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 2 ms 500 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 2 ms 560 KB Output is correct
7 Correct 2 ms 612 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 2 ms 724 KB Output is correct
11 Correct 2 ms 724 KB Output is correct
12 Correct 2 ms 724 KB Output is correct
13 Correct 3 ms 724 KB Output is correct

Subtask #2
75.0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 724 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 2 ms 724 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 2 ms 724 KB Output is correct
11 Correct 2 ms 724 KB Output is correct
12 Correct 2 ms 724 KB Output is correct
13 Correct 2 ms 724 KB Output is correct
14 Correct 2 ms 724 KB Output is correct
15 Correct 2 ms 724 KB Output is correct
16 Correct 2 ms 724 KB Output is correct

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 135 ms 724 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 133 ms 772 KB Output is correct
4 Correct 102 ms 884 KB Output is correct
5 Correct 80 ms 1092 KB Output is correct
6 Correct 35 ms 1092 KB Output is correct
7 Correct 21 ms 1108 KB Output is correct
8 Correct 131 ms 1268 KB Output is correct
9 Correct 132 ms 1268 KB Output is correct
10 Correct 132 ms 1396 KB Output is correct
11 Correct 132 ms 1396 KB Output is correct
12 Correct 132 ms 1540 KB Output is correct
13 Correct 133 ms 1672 KB Output is correct
14 Correct 152 ms 1672 KB Output is correct
15 Correct 133 ms 1716 KB Output is correct
16 Correct 135 ms 1764 KB Output is correct
17 Correct 134 ms 1896 KB Output is correct