Submission #156067

#	Time	Username	Problem	Language	Result	Execution time	Memory
156067		EntityIT	도장 모으기 (JOI14_stamps)	C++14	100 / 100	460 ms	141876 KiB

stamps

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;
const LL infLL = (LL)1e18 + 123;
const int N = (int)3e3 + 5;

void assignMin(LL &a, LL b) {
    a = min(a, b);
}

int n, t, u[N], v[N], d[N], e[N];
LL dp[2][N][N];

int main() {
    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 = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) dp[0][i][j] = dp[1][i][j] = infLL;
    }
    dp[0][1][0] = t;
    for (int i = 1; i <= n; ++i) {
        for (int j = n; j > 0; --j) assignMin(dp[1][i][j - 1], dp[0][i][j] + u[i] + e[i]);
        for (int j = n; j > 0; --j) assignMin(dp[1][i][j - 1], dp[1][i][j] + u[i] + e[i]);
        for (int j = 0; j < n; ++j) assignMin(dp[1][i][j + 1], dp[0][i][j] + d[i] + v[i]);
        for (int j = 0; j < n; ++j) assignMin(dp[1][i][j + 1], dp[1][i][j] + d[i] + v[i]);
        for (int j = 0; j <= n; ++j) {
            assignMin(dp[1][i][j], dp[0][i][j] + u[i] + v[i]);
            if (j) assignMin(dp[1][i][j], dp[0][i][j] + d[i] + e[i]);
        }
        for (int j = 0; j <= n; ++j) assignMin(dp[0][i + 1][j], dp[1][i][j] + t + 2 * j * t);
    }

    printf("%lld", dp[1][n][0] + t);

    return 0;
}

Compilation message (stderr)

stamps.cpp: In function 'int main()':
stamps.cpp:17: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:18:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int i = 1; i <= n; ++i) 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