Submission #995589

#	Time	Username	Problem	Language	Result	Execution time	Memory
995589		amine_aroua	Pinball (JOI14_pinball)	C++17	0 / 100	1 ms	4964 KiB

pinball

#include <bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
using namespace std;
#define intt long long
#define pb push_back
#define nl '\n'
#define fore(i, y) for(int i = 0; i < y; i++)
#define forr(i, x, y) for(int i = x;i<=y;i++)
#define forn(i, y, x) for(int i = y; i >= x; i--)
const int M = 3e5 + 10;
intt dp[2][M];
intt n , m;
vector<tuple<intt , intt , intt,intt>> intervals;
const intt INF = 1e18;
void initDP()
{
    fore(i , 2)
    {
        fore(j , M)
        {
            dp[i][j] = INF;
        }
    }
}
void rakkah()
{
    map<intt ,intt> compress;
    forr(i , 1 , m)
    {
        intt a , b , c , d;
        cin>>a>>b>>c>>d;
        compress[a] = compress[b] = compress[c] = 1;
        intervals.pb({a , b , c , d});
    }
    intt cnt = 0;
    for(auto p : compress)
    {
        compress[p.first] = cnt++;
    }
    n = cnt - 1;
    for(auto &[a , b , c , d] : intervals)
    {
        a = compress[a] , b = compress[b] , c = compress[c];
    }
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    initDP();
    cin>>m>>n;
    rakkah();
    intt ans = INF;
    fore(i , m)
    {
        auto [a , b , c ,d] = intervals[i];
        if(a == 0)
            dp[0][c] = d;
        if(b == n)
            dp[1][c] = d;
        forr(x , a , b)
        {
            fore(j , 2)
            {
                dp[j][c] = min(dp[j][c] , d + dp[j][x]);
            }
        }
        ans = min(ans , dp[0][c] + dp[1][c] - d);
    }
    cout<<(ans >= 1e16 ? -1 : ans)<<nl;
}

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