oj.uz

Submission #958980

# Submission time Handle Problem Language Result Execution time Memory
958980 2024-04-07T10:42:33 Z typ_ik Pinball (JOI14_pinball) C++17
11 / 100
 4 ms 6748 KB 
#include <bits/stdc++.h>

#define ll long long
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define watch(x) cout << (#x) << " : " << x << '\n'
#define boost ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

const int N = 100100;
int l[N], r[N], c[N], d[N];

ll pref[N], suf[N];
const ll INF = 1e16 + 128;

void solve() {
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < n; i++)
        cin >> l[i] >> r[i] >> c[i] >> d[i];

    for (int i = 1; i <= m; i++)
        pref[i] = suf[i] = INF;
    pref[0] = 0;
    suf[m + 1] = 0;

    ll ans = INF;
    for (int i = 0; i < n; i++) {
        ll lx = INF, rx = INF;
        if (l[i] == 1) lx = 0;
        if (r[i] == m) rx = 0;

        for (int x = l[i]; x <= r[i]; x++)
            lx = min(lx, pref[x]), rx = min(rx, suf[x]);

        ans = min(ans, lx + rx + d[i]);

        if (l[i] == 1)
            pref[c[i]] = min(pref[c[i]], 1ll * d[i]);
        else for (int x = l[i]; x <= r[i]; x++)
            pref[c[i]] = min(pref[c[i]], pref[x] + d[i]);

        if (r[i] == m)
            suf[c[i]] = min(suf[c[i]], 1ll * d[i]);
        else for (int x = l[i]; x <= r[i]; x++)
            suf[c[i]] = min(suf[c[i]], suf[x] + d[i]);
    }

    if (ans >= INF)
        ans = -1;

    cout << ans << '\n';
}

main() {
    boost;
    solve();
    return 0;
}

Compilation message

pinball.cpp:57:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   57 | main() {
      | ^~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2468 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2480 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2468 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2480 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Runtime error 4 ms 6748 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2468 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2480 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Runtime error 4 ms 6748 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2468 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2480 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Runtime error 4 ms 6748 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -