제출 #156050

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
156050		atoiz	도장 모으기 (JOI14_stamps)	C++14	100 / 100	165 ms	71244 KiB

stamps

#include <iostream>
#include <algorithm>

using namespace std;

const int MAXN = 3007;
const long long INF = 1e15;
int n;
long long u[MAXN], v[MAXN], d[MAXN], e[MAXN], t, f[MAXN][MAXN];
void upd(long long &x, long long y) { if (x > y) x = y; }

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> t;
    for (int i = 1; i <= n; ++i) cin >> u[i] >> v[i] >> d[i] >> e[i];
    for (int i = 1; i <= n + 1; ++i) for (int j = 0; j <= n + 1; ++j) f[i][j] = INF;
    f[1][0] = 0;

    for (int i = 1; i <= n; ++i) {
        for (int j = n; j > 0; --j) if (f[i][j] < INF) upd(f[i][j - 1], f[i][j] + u[i] + e[i]);
        for (int j = 0; j < n; ++j) if (f[i][j] < INF) upd(f[i][j + 1], f[i][j] + d[i] + v[i]);

        for (int j = n; j >= 0; --j) if (f[i][j] < INF) {
            upd(f[i + 1][j], f[i][j] + u[i] + v[i] + j * t * 2);
            upd(f[i + 1][j + 1], f[i][j] + d[i] + v[i] + (j + 1) * t * 2);
            if (j > 0) upd(f[i + 1][j], f[i][j] + d[i] + e[i] + j * t * 2);
            if (j > 0) upd(f[i + 1][j - 1], f[i][j] + u[i] + e[i] + (j - 1) * t * 2);
        }
    }
    cout << f[n + 1][0] + t * (n + 1) << endl;
}

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