Submission #995587

#TimeUsernameProblemLanguageResultExecution timeMemory
995587amine_arouaPinball (JOI14_pinball)C++17
0 / 100
1 ms4956 KiB
#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 == INF ? -1 : ans)<<nl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...