fork(2) download 
  1. #include<bits/stdc++.h>
  2. #define ll long long int
  3. using namespace std;
  4. int main()
  5. {
  6.     ll n,k,u,v,w,days;
  7.     cin>>n>>k;
  8.     vector<pair<ll,pair<ll,ll> > > deal;//(w,(u,v))
  9.     vector<pair<ll,ll> > pack[k];
  10.     vector<ll> pack1[k],pack2[k];
  11.     for(ll i=0;i<n;i++)
  12.     {
  13.         cin>>u>>v>>w;
  14.         days=v-u+1;
  15.         if(days>=k)
  16.             continue;
  17.         deal.push_back({w,{u,v}});
  18.         pack[days].push_back({u,w});
  19.     }
  20.     for(ll i=0;i<k;i++)
  21.         sort(pack[i].begin(),pack[i].end());
  22.     for(ll i=0;i<k;i++)
  23.     {
  24.         for(ll j=0;j<pack[i].size();j++)
  25.         {
  26.             pack1[i].push_back(pack[i][j].first);
  27.             pack2[i].push_back(pack[i][j].second);
  28.         }
  29.         ll mini=1e18;
  30.         if(pack2[i].size()==0)
  31.             continue;
  32.         for(ll j=pack2[i].size()-1;j>=0;j--)
  33.         {
  34.             mini=min(mini,pack2[i][j]);
  35.             pack2[i][j]=mini;
  36.         }
  37.     }
  38.     ll ans=1e18;
  39.     for(ll i=0;i<deal.size();i++)
  40.     {
  41.         ll cost=deal[i].first;
  42.         u=deal[i].second.first;
  43.         v=deal[i].second.second;
  44.         days=v-u+1;
  45.         ll left=k-days;
  46.         days=left;
  47.         //search in pack1[days]
  48.         v++;
  49.         ll pos=lower_bound(pack1[days].begin(),pack1[days].end(),v)-pack1[days].begin();
  50.         if(pos==pack1[days].size())
  51.             continue;
  52.         cost+=pack2[days][pos];
  53.         ans=min(ans,cost);
  54.     }
  55.     if(ans==1e18)
  56.         cout<<-1;
  57.     else
  58.         cout<<ans;
  59. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin 
4 5
1 3 4
1 2 5
5 6 1
1 2 4
stdout 
5
https://ideone.com/9KgcSL
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!