Submission #94852

#TimeUsernameProblemLanguageResultExecution timeMemory
94852easruiPinball (JOI14_pinball)C++14
51 / 100
52 ms16248 KiB
#include <bits/stdc++.h> using namespace std; const int MaxM = 1010; const long long INF = 1e15; int M,N; long long ans=INF,cnt,DL[MaxM][MaxM],DR[MaxM][MaxM]; struct Pin { int A,B,C,D; } P[MaxM]; vector<int> pos; int main() { //freopen("input.txt","r",stdin); ios_base::sync_with_stdio(0),cin.tie(0); cin >> M >> N; for(int i=1; i<=M; i++) { cin >> P[i].A >> P[i].B >> P[i].C >> P[i].D; pos.push_back(P[i].C); } pos.push_back(1); pos.push_back(N); sort(pos.begin(),pos.end()); pos.erase(unique(pos.begin(),pos.end()),pos.end()); for(int i=1; i<=M; i++) { P[i].A = lower_bound(pos.begin(),pos.end(),P[i].A)-pos.begin(); P[i].B = upper_bound(pos.begin(),pos.end(),P[i].B)-pos.begin()-1; P[i].C = lower_bound(pos.begin(),pos.end(),P[i].C)-pos.begin(); } int sz = pos.size(); for(int i=0; i<=M; i++) { for(int l=0; l<sz; l++) DL[l][i] = INF; for(int r=0; r<sz; r++) DR[r][i] = INF; } DL[0][0] = 0; DR[sz-1][0] = 0; for(int i=0; i<M; i++) { for(int l=sz-1; l>=0; l--) { if(l<sz-1) DL[l][i] = min(DL[l][i],DL[l+1][i]); DL[l][i+1] = min(DL[l][i+1],DL[l][i]); bool left = P[i+1].A<=l && l<P[i+1].C; if(left) DL[P[i+1].C][i+1] = min(DL[P[i+1].C][i+1],DL[l][i]+P[i+1].D); } for(int r=0; r<sz; r++) { if(r>0) DR[r][i] = min(DR[r][i],DR[r-1][i]); DR[r][i+1] = min(DR[r][i+1],DR[r][i]); bool right = P[i+1].B>=r && r>P[i+1].C; if(right) DR[P[i+1].C][i+1] = min(DR[P[i+1].C][i+1],DR[r][i]+P[i+1].D); } } for(int i=1; i<=M; i++) ans = min(ans,DL[P[i].A][i-1]+DR[P[i].B][i-1]+P[i].D); if(ans==INF) cout << -1; else cout << ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...