Submission #245296

#	Time	Username	Problem	Language	Result	Execution time	Memory
245296		thecodingwizard	Pinball (JOI14_pinball)	C++11	51 / 100	1091 ms	2040 KiB

pinball

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const ll inf = 1e18;

int main() {
    int m, n; cin >> m >> n;
    int L[m], R[m], T[m], C[m];
    for (int i = 0; i < m; i++) cin >> L[i] >> R[i] >> T[i] >> C[i];
    ll dpLeft[m], dpRight[m];
    for (int i = 0; i < m; i++) {
        dpLeft[i] = dpRight[i] = inf;

        if (L[i] == 1) dpLeft[i] = C[i];
        if (R[i] == n) dpRight[i] = C[i];

        for (int j = 0; j < i; j++) {
            if (L[i] <= T[j] && T[j] <= R[i]) {
                dpLeft[i] = min(dpLeft[i], dpLeft[j] + C[i]);
                dpRight[i] = min(dpRight[i], dpRight[j] + C[i]);
            }
        }
    }

    ll opt = inf;

    for (int i = 0; i < m; i++) {
        opt = min(opt, dpLeft[i] + dpRight[i] - C[i]);
    }

    if (opt == inf) cout << -1 << endl;
    else cout << opt << endl;

    return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 0 / 49