oj.uz

Submission #142480

# Submission time Handle Problem Language Result Execution time Memory
142480 2019-08-09T08:47:43 Z alextodoran Pinball (JOI14_pinball) C++14
0 / 100
 2 ms 632 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];

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;
    for(int i = 0; i < objects.size(); i++)
    {
        if(i > 0 && objects[i].pos > objects[i - 1].pos)
            pos++;
        if(objects[i].pos - objects[i - 1].pos > 1 && objects[i].type == 'L' && objects[i - 1].type == 'R')
        {
            cout << "-1\n";
            return 0;
        }
        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:62: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
0 / 11.0

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

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 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 Incorrect 2 ms 376 KB Output isn't correct
3 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 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -