oj.uz

Submission #995605

# Submission time Handle Problem Language Result Execution time Memory
995605 2024-06-09T12:41:24 Z amine_aroua Pinball (JOI14_pinball) C++17
0 / 100
 1 ms 4956 KB 
#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;
    compress[n] = 1;
    compress[1] = 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 = 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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 1 ms 4956 KB Output is correct
7 Correct 1 ms 4956 KB Output is correct
8 Incorrect 1 ms 4956 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 1 ms 4956 KB Output is correct
7 Correct 1 ms 4956 KB Output is correct
8 Incorrect 1 ms 4956 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 1 ms 4956 KB Output is correct
7 Correct 1 ms 4956 KB Output is correct
8 Incorrect 1 ms 4956 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 1 ms 4956 KB Output is correct
7 Correct 1 ms 4956 KB Output is correct
8 Incorrect 1 ms 4956 KB Output isn't correct
9 Halted 0 ms 0 KB -