Submission #142536

#	Time	Username	Problem	Language	Result	Execution time	Memory
142536		alextodoran	Pinball (JOI14_pinball)	C++14	29 / 100	1068 ms	41084 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 lvn[N_MAX], rvn[N_MAX];
int lvp[N_MAX], rvp[N_MAX];

int start[N_MAX];

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;
            lv[++cntl] = pos;
        }
        if(objects[i].type == 'R')
        {
            devices[objects[i].index].r = pos;
            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;
    ll ans = INF;
    start[cntl + 1] = cntr + 1;
    for(int j1 = cntl; j1 >= 1; j1--)
    {
        start[j1] = start[j1 + 1];
        int l = lv[j1];
        while(start[j1] > 1 && rv[start[j1] - 1] >= l)
            start[j1]--;
    }
    for(int i = 1; i <= cntl; i++)
    {
        lvn[i] = i + 1;
        lvp[i] = i - 1;
    }
    for(int i = 1; i <= cntr; i++)
    {
        rvn[i] = i + 1;
        rvp[i] = i - 1;
    }
    for(int i = 1; i <= m; i++)
    {
        for(int j1 = cntl; j1 >= 1; j1--)
            if(lv[j1] != -1)
            {
                int l = lv[j1];
                for(int j2 = start[j1]; j2 <= cntr; j2++)
                    if(rv[j2] != -1)
                    {
                        int r = rv[j2];
                        dp[i & 1][l][r] = min(dp[(i & 1) ^ 1][l][r], min(dp[i & 1][lv[lvn[j1]]][r], dp[i & 1][l][rv[rvp[j2]]]));
                        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 j = 1; j <= cntl; j++)
            if(lv[j] == devices[i].l)
            {
                lvn[lvp[j]] = lvn[j];
                lvp[lvn[j]] = lvp[j];
                lv[j] = -1;
                break;
            }
        for(int j = 1; j <= cntr; j++)
            if(rv[j] == devices[i].r)
            {
                rvn[rvp[j]] = rvn[j];
                rvp[rvn[j]] = rvp[j];
                rv[j] = -1;
                break;
            }
    }
    if(ans == INF)
        cout << "-1\n";
    else
        cout << ans << "\n";
    return 0;
}

Compilation message (stderr)

pinball.cpp: In function 'int main()':
pinball.cpp:76:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < objects.size(); i++)
                    ~~^~~~~~~~~~~~~~~~
pinball.cpp:155: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:38: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