oj.uz

Submission #366509

# Submission time Handle Problem Language Result Execution time Memory
366509 2021-02-14T10:15:23 Z idk321 Pinball (JOI14_pinball) C++11
0 / 100
 1 ms 620 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll M = 1000000000000000000LL;
const int N = 205;


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

    int m, n;
    cin >> m >> n;
    vector<array<int, 4>> devices(m);
    set<int> values;
    values.insert(1);
    values.insert(n);
    for (int i = 0; i < m; i++)
    {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        devices[i][0] = a;
        values.insert(a);
        devices[i][1] = b;
        values.insert(b);
        devices[i][2] = c;
        devices[i][3] = d;
    }

    map<int, int> to;
    int curTo = 1;
    for (int i : values)
    {
        to[i] = curTo;
        curTo++;
    }
    n = to[n];
    for (auto& device : devices)
    {
        for (int i = 0; i <= 2; i++) device[i] = to[device[i]];
    }

    ll dp[N][N];
    for (int i = 0; i <N; i++) for (int j = 0; j < N; j++) dp[i][j] = M;
    for (int i = m - 1; i >= 0; i--)
    {
        int x = devices[i][0];
        int y = devices[i][1];
        int c = devices[i][2];
        int d = devices[i][3];
        dp[x][y] = min<ll>(dp[x][y], d);
        for (int j = 1; j <= n; j++)
        {
            for (int k = j; k <= n; k++)
            {
                if (c >= j && c <= k)
                {
                    dp[min(j, x)][max(k, y)] = min(dp[min(j, x)][max(k, y)], dp[j][k] + d);

                }
            }
        }

    }



    if (dp[1][n] == M) cout << -1 << "\n";
    else cout << dp[1][n] << "\n";
}

/*
5 6
2 4 3 5
1 2 2 8
3 6 5 2
4 6 4 7
2 4 3 10
*/

/*
6 6
2 4 3 5
1 2 2 8
3 6 5 2
4 6 4 7
2 4 3 10
1 5 1 4
*/

/*
3 5
2 4 3 10
1 3 1 20
2 5 4 30
*/

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Incorrect 1 ms 620 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Incorrect 1 ms 620 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Incorrect 1 ms 620 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Incorrect 1 ms 620 KB Output isn't correct
4 Halted 0 ms 0 KB -