Submission #1305091

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305091		lsjo	Pinball (JOI14_pinball)	C++20	29 / 100	1095 ms	8312 KiB

pinball

#include <bits/stdc++.h>
using namespace std;
#define int long long

int a[1005],b[1005],c[1005],d[1005];
int dp[1005][1005];
int currl[1005];
int currr[1005];

const int inf = 1e18;

signed main() {
    for (int i = 0; i <= 1000; i++) {
        for (int j = 0; j <= 1000; j++) dp[i][j]=inf;
    }
    
    int m, n; cin >> m >> n;
    for (int i = 0; i < m; i++) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
    }

    for (int i = m-1; i >= 0; i--) {
        dp[i][i]=d[i];
        // find the continuous to left for each thing
        // and smallest continuous to right
        // then use curr to merge them

        //cout << i << "\n";

        for (int j = 0; j < m; j++) {
            for (int k = 0; k < m; k++) {
                if (a[j] <= b[k] && a[j] <= a[i] && a[i] <= b[k] && b[k] <= b[i]) { // checking if they overlap correctly
                    // checking if c[i] puts it in the thing
                    if (a[j] <= c[i] && c[i] <= b[k]) dp[j][i] = min(dp[j][i], dp[j][k]+d[i]);
                }
                if (a[j] <= b[k] && a[i] <= a[j] && a[j] <= b[i] && b[i] <= b[k]) {
                    if (a[j] <= c[i] && c[i] <= b[k]) dp[i][k] = min(dp[i][k], dp[j][k]+d[i]);
                }
            }
        }

        /*for (int j = 0; j < m; j++) {
            for (int k = 0; k < m; k++) {
                cout << dp[j][k] << " ";
            }
            cout << "\n";
        }

        cout << "\n";*/

        //cout << dp[i][i] << "\n";
    }

    int minnum = inf;

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < m; j++) {
            if (a[i]==1 && b[j]==n) minnum=min(minnum, dp[i][j]);
        }
    }

    if (minnum==inf) cout << -1 << "\n";
    else cout << minnum << "\n";
    return 0;
}

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