Submission #48309

#	Time	Username	Problem	Language	Result	Execution time	Memory
48309		choikiwon	도장 모으기 (JOI14_stamps)	C++17	85 / 100	1123 ms	262144 KiB

stamps

#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 - idx) 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 (stderr)

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 / 10
• Subtask 2: 75 / 75
• Subtask 3: 0 / 15