oj.uz

답안 #48307

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
48307 2018-05-11T16:09:16 Z choikiwon 도장 모으기 (JOI14_stamps) C++17
85 / 100
 1000 ms 262144 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 cc[MN][MN][2][2];
int dp(int idx, int open, int t, int d) {
    if(idx == N) return open? 1e9 : 0;
    int &ret = cc[idx][open][t][d];
    if(ret != -1) return ret;

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

    return ret;
}

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]);
    }

    memset(cc, -1, sizeof(cc));
    printf("%d", T + dp(0, 0, 1, 0));
}

Compilation message

stamps.cpp: In function 'int main()':
stamps.cpp:34: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:37: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 99 ms 142200 KB Output is correct
2 Correct 99 ms 142324 KB Output is correct
3 Correct 100 ms 142404 KB Output is correct
4 Correct 100 ms 142492 KB Output is correct
5 Correct 100 ms 142492 KB Output is correct
6 Correct 101 ms 142512 KB Output is correct
7 Correct 104 ms 142576 KB Output is correct
8 Correct 101 ms 142576 KB Output is correct
9 Correct 103 ms 142576 KB Output is correct
10 Correct 101 ms 142576 KB Output is correct
11 Correct 104 ms 142576 KB Output is correct
12 Correct 100 ms 142576 KB Output is correct
13 Correct 101 ms 142576 KB Output is correct

Subtask #2
75.0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 106 ms 144236 KB Output is correct
2 Correct 102 ms 144236 KB Output is correct
3 Correct 104 ms 144632 KB Output is correct
4 Correct 101 ms 144632 KB Output is correct
5 Correct 102 ms 144632 KB Output is correct
6 Correct 101 ms 144632 KB Output is correct
7 Correct 104 ms 144632 KB Output is correct
8 Correct 103 ms 144632 KB Output is correct
9 Correct 111 ms 144632 KB Output is correct
10 Correct 104 ms 144632 KB Output is correct
11 Correct 106 ms 144772 KB Output is correct
12 Correct 105 ms 144772 KB Output is correct
13 Correct 103 ms 144772 KB Output is correct
14 Correct 100 ms 144772 KB Output is correct
15 Correct 104 ms 144772 KB Output is correct
16 Correct 102 ms 144772 KB Output is correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1055 ms 262144 KB Time limit exceeded
2 Halted 0 ms 0 KB -