Submission #48318

#	Time	Username	Problem	Language	Result	Execution time	Memory
48318		choikiwon	도장 모으기 (JOI14_stamps)	C++17	100 / 100	142 ms	796 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 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));
                        }
                    }
                }
            }
        }
    }

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

Compilation message (stderr)

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