Submission #1069996

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069996		juicy	도장 모으기 (JOI14_stamps)	C++17	100 / 100	44 ms	35912 KiB

stamps

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 3005, inf = 1e9;

int n, t;
int a[N], b[N], lt[N], rt[N], dp[N][N];

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);

    cin >> n >> t;
    for (int i = 1; i <= n; ++i) {
        int u, v, d, e; cin >> u >> v >> d >> e;
        a[i] = u + v;
        b[i] = d + e;
        rt[i] = u + e + 2 * t * i;
        lt[i] = v + d - 2 * t * i;
    }  
    memset(dp, 0x3f, sizeof(dp));
    dp[0][0] = 0;
    for (int i = 1; i <= n; ++i) {
        int mn = inf;
        for (int j = 0; j <= n; ++j) {
            dp[i][j] =  min(dp[i][j], mn);
            mn = min(mn, dp[i - 1][j]);
            mn = min(inf, mn + lt[i]);
            dp[i][j] = min(dp[i][j], dp[i - 1][j] + a[i]);
            if (j > 0) {
                dp[i][j] = min(dp[i][j], dp[i - 1][j] + b[i]);
            } 
        }
        mn = inf;
        for (int j = n; j >= 0; --j) {
            dp[i][j] = min(dp[i][j], mn);
            mn = min(mn, dp[i - 1][j]);
            mn = min(inf, mn + rt[i]);
        }
    }  
    cout << dp[n][0] + t * (n + 1);
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 75 / 75
• Subtask 3: 15 / 15