Codeforces Round #422 (Div. 2), problem: (C) Hacker, pack your bags Solution In C/C++

By | 2017-07-25T09:01:08+00:00 July 25th, 2017|Categories: C/C++, Programming|Tags: , , , , , , , , |

#include<cstdio> #include<vector> #include<cstring> #include<algorithm> #define ll long long using namespace std; ll ans,c[200101],n,x,L,R,cc; vector<pair<ll,ll> >l[200101],r[200101]; int main(){ scanf("%lld%lld",&n,&x); for(int i=1;i<=n;i++){ scanf("%lld%lld%lld",&L,&R,&cc); l[L].push_back(make_pair(R-L+1,cc)); r[R].push_back(make_pair(R-L+1,cc)); } memset(c,0x3f3f,sizeof(c));ans=c[0]; for(int i=1;i<200100;i++){ for(int j=0;j<l[i].size();j++)l[i][j].first>=x?0:ans=min(ans,c[x-l[i][j].first]+l[i][j].second); for(int j=0;j<r[i].size();j++)c[r[i][j].first]=min(c[r[i][j].first],r[i][j].second); } printf("%lld",ans==c[0]?-1:ans); return 0; }