Submission #142498

#	Time	Username	Problem	Language	Result	Execution time	Memory
142498		alextodoran	Pinball (JOI14_pinball)	C++14	29 / 100	1064 ms	41080 KiB

pinball

#include <bits/stdc++.h>

#define M_MAX 1002
#define N_MAX 3002
#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[2][N_MAX][N_MAX];

set <int> active;

int lv[N_MAX], rv[N_MAX];
int cntl, cntr;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    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(pos > lv[cntl])
                lv[++cntl] = pos;
        }
        if(objects[i].type == 'R')
        {
            devices[objects[i].index].r = pos;
            if(pos > rv[cntr])
                rv[++cntr] = 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 <= 1; 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;
    int startR = cntr + 1;
    ll ans = INF;
    for(int i = 1; i <= m; i++)
    {
        for(int j1 = cntl; j1 >= 1; j1--)
        {
            int l = lv[j1];
            while(startR > 1 && rv[startR - 1] >= l)
                startR--;
            for(int j2 = startR; j2 <= cntr; j2++)
            {
                int r = rv[j2];
                dp[i & 1][l][r] = min(dp[(i & 1) ^ 1][l][r], min(dp[i & 1][lv[j1 + 1]][r], dp[i & 1][l][rv[j2 - 1]]));
                if(devices[i].hole >= l && devices[i].hole <= r)
                {
                    int l1 = l, r1 = r;
                    l1 = min(l1, devices[i].l);
                    r1 = max(r1, devices[i].r);
                    dp[i & 1][l][r] = min(dp[i & 1][l][r], dp[(i & 1) ^ 1][l1][r1] + devices[i].cost);
                }
            }
        }
        ans = min(ans, dp[i & 1 ^ 1][devices[i].l][devices[i].r] + devices[i].cost);
    }
    for(int i = 1; i <= n; i++)
        ans = min(ans, dp[m & 1][i][i]);
    if(ans == INF)
        cout << "-1\n";
    else
        cout << ans << "\n";
    return 0;
}

Compilation message (stderr)

pinball.cpp: In function 'int main()':
pinball.cpp:71:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < objects.size(); i++)
                    ~~^~~~~~~~~~~~~~~~
pinball.cpp:135:29: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
         ans = min(ans, dp[i & 1 ^ 1][devices[i].l][devices[i].r] + devices[i].cost);
                           ~~^~~
pinball.cpp: In function 'int f(char)':
pinball.cpp:37:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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