Submission #94846

#TimeUsernameProblemLanguageResultExecution timeMemory
94846easruiPinball (JOI14_pinball)C++14
29 / 100
110 ms98092 KiB
#include <bits/stdc++.h> using namespace std; const int MaxM = 210; const long long INF = 1e15; int M,N; long long ans=INF,cnt,DP[MaxM][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++) for(int r=l; r<sz; r++) DP[l][r][i] = INF; DP[0][sz-1][0] = 0; for(int i=0; i<M; i++) { for(int l=0; l<sz; l++) { for(int r=l; r<sz; r++) { DP[l][r][i+1] = min(DP[l][r][i+1],DP[l][r][i]); bool left = P[i+1].A<=l && l<P[i+1].C, right = P[i+1].B>=r && r>P[i+1].C; cnt = DP[l][r][i]+P[i+1].D; if(P[i+1].A<=l && P[i+1].B>=r) DP[P[i+1].C][P[i+1].C][i+1] = min(DP[P[i+1].C][P[i+1].C][i+1],cnt); else { if(left) DP[P[i+1].C][r][i+1] = min(DP[P[i+1].C][r][i+1],cnt); if(right) DP[l][P[i+1].C][i+1] = min(DP[l][P[i+1].C][i+1],cnt); } } } } for(int i=0; i<sz; i++) ans = min(ans,DP[i][i][M]); 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...