oj.uz

Submission #142481

# Submission time Handle Problem Language Result Execution time Memory
142481 2019-08-09T09:02:43 Z alextodoran Pinball (JOI14_pinball) C++14
11 / 100
 412 ms 524292 KB 
#include <bits/stdc++.h>

#define M_MAX 202
#define N_MAX 602
#define ll long long

using namespace std;

const ll INF = 100000000000000001;

struct Device
{
    int l, r;
    int hole;
    ll cost;
};

int n, m;

Device devices[M_MAX];

struct Object
{
    int pos;
    char type;
    int index;
};

int f (char type)
{
    if(type == 'L')
        return 1;
    if(type == 'H')
        return 2;
    if(type == 'R')
        return 3;
}

bool operator < (const Object &a, const Object &b)
{
    if(a.pos != b.pos)
        return a.pos < b.pos;
    return f(a.type) < f(b.type);
}

vector <Object> objects;

ll dp[M_MAX][N_MAX][N_MAX];

set <int> active;

int main()
{
    cin >> m >> n;
    for(int i = 1; i <= m; i++)
    {
        cin >> devices[i].l >> devices[i].r >> devices[i].hole >> devices[i].cost;
        objects.push_back(Object{devices[i].l, 'L', i});
        objects.push_back(Object{devices[i].r, 'R', i});
        objects.push_back(Object{devices[i].hole, 'H', i});
    }
    sort(objects.begin(), objects.end());
    int pos = 1;
    int lastR = 0;
    for(int i = 0; i < objects.size(); i++)
    {
        if(i > 0 && active.empty() && objects[i].pos - lastR > 1)
        {
            cout << "-1\n";
            return 0;
        }
        if(objects[i].type == 'L')
            active.insert(objects[i].index);
        else if(objects[i].type == 'R')
        {
            lastR = objects[i].pos;
            active.erase(objects[i].index);
        }
        if(i > 0 && objects[i].pos > objects[i - 1].pos)
            pos++;
        if(objects[i].type == 'L')
            devices[objects[i].index].l = pos;
        if(objects[i].type == 'R')
            devices[objects[i].index].r = pos;
        if(objects[i].type == 'H')
            devices[objects[i].index].hole = pos;
    }
    if(n > objects.back().pos || objects.front().pos > 1)
    {
        cout << "-1\n";
        return 0;
    }
    n = pos;
    for(int i = 0; i <= m; i++)
        for(int l = 0; l <= n + 1; l++)
            for(int r = 0; r <= n + 1; r++)
                dp[i][l][r] = INF;
    dp[0][1][n] = 0;
    for(int i = 1; i <= m; i++)
        for(int l = n; l >= 1; l--)
            for(int r = l; r <= n; r++)
            {
                dp[i][l][r] = min(dp[i - 1][l][r], min(dp[i][l + 1][r], dp[i][l][r - 1]));
                if(devices[i].hole < l || devices[i].hole > r)
                    continue;
                int l1 = l, r1 = r;
                l1 = min(l1, devices[i].l);
                r1 = max(r1, devices[i].r);
                dp[i][l][r] = min(dp[i][l][r], dp[i - 1][l1][r1] + devices[i].cost);
            }
    ll ans = INF;
    for(int i = 1; i <= n; i++)
        ans = min(ans, dp[m][i][i]);
    if(ans == INF)
        cout << "-1\n";
    else
        cout << ans << "\n";
    return 0;
}

Compilation message

pinball.cpp: In function 'int main()':
pinball.cpp:65:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < objects.size(); i++)
                    ~~^~~~~~~~~~~~~~~~
pinball.cpp: In function 'int f(char)':
pinball.cpp:37:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 2 ms 1016 KB Output is correct
3 Correct 3 ms 1400 KB Output is correct
4 Correct 3 ms 1656 KB Output is correct
5 Correct 3 ms 1656 KB Output is correct
6 Correct 2 ms 760 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 1016 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 2 ms 1016 KB Output is correct
3 Correct 3 ms 1400 KB Output is correct
4 Correct 3 ms 1656 KB Output is correct
5 Correct 3 ms 1656 KB Output is correct
6 Correct 2 ms 760 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 1016 KB Output is correct
9 Correct 63 ms 76796 KB Output is correct
10 Correct 162 ms 191580 KB Output is correct
11 Correct 224 ms 255136 KB Output is correct
12 Runtime error 412 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 2 ms 1016 KB Output is correct
3 Correct 3 ms 1400 KB Output is correct
4 Correct 3 ms 1656 KB Output is correct
5 Correct 3 ms 1656 KB Output is correct
6 Correct 2 ms 760 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 1016 KB Output is correct
9 Correct 63 ms 76796 KB Output is correct
10 Correct 162 ms 191580 KB Output is correct
11 Correct 224 ms 255136 KB Output is correct
12 Runtime error 412 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 2 ms 1016 KB Output is correct
3 Correct 3 ms 1400 KB Output is correct
4 Correct 3 ms 1656 KB Output is correct
5 Correct 3 ms 1656 KB Output is correct
6 Correct 2 ms 760 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 1016 KB Output is correct
9 Correct 63 ms 76796 KB Output is correct
10 Correct 162 ms 191580 KB Output is correct
11 Correct 224 ms 255136 KB Output is correct
12 Runtime error 412 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Halted 0 ms 0 KB -