Submission #995613

#	Time	Username	Problem	Language	Result	Execution time	Memory
995613		amine_aroua	Pinball (JOI14_pinball)	C++17	51 / 100	1029 ms	18780 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 , o;
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;
    o = 1;
    compress[n] = 1;
    compress[o] = 1;
    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 = compress[n] ;
    o = compress[o];
    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];
        intt cur[2] = {INF , INF};
        if(a == o)
            cur[0] = d;
        if(b == n)
            cur[1] = d;
        forr(x , a , b)
        {
            fore(j , 2)
            {
                cur[j] = min(cur[j] , d + dp[j][x]);
            }
        }
        fore(j , 2)
            dp[j][c] = min(dp[j][c] , cur[j]);
        ans = min(ans , cur[0] + cur[1] - d);
    }
    cout<<(ans >= 1e17 ? -1 : ans)<<nl;
}

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