fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ii pair<ll,ll>
  3. #define iii pair<ll,pair<ll,ll>>
  4. #define ll long long
  5. #define file(a) freopen(a".inp","r",stdin);freopen(a".out","w",stdout);
  6. using namespace std;
  7. const int maxn = 1e6+5;
  8. string s;
  9. ll n,m,k,st[4*maxn],lazy[4*maxn],a[maxn],q,ans[maxn],dp[maxn];
  10. map<ll,ll> last;
  11. void down(ll id,ll l,ll r,ll mid)
  12. {
  13.     if (lazy[id] != 0)
  14.     {
  15.         lazy[id*2] = lazy[id];
  16.         st[id*2] = (mid-l+1) * lazy[id];
  17.  
  18.         lazy[id*2+1] = lazy[id];
  19.         st[id*2+1] = (r-mid) * lazy[id];
  20.  
  21.         lazy[id] = 0;
  22.     }
  23. }
  24. void update(ll u, ll v, ll val, ll id=1, ll l=1, ll r=n)
  25. {
  26.     // [l,r] pos [l,r]
  27.     if (l > v || r < u) return;
  28.     if (u <= l && r <= v)
  29.     {
  30.         st[id] = (r-l+1) * val;
  31.         lazy[id] = val;
  32.         return;
  33.     }
  34.  
  35.     ll mid = (l+r) >> 1;
  36.     down(id,l,r,mid);
  37.     update(u,v,val,id*2,l,mid);
  38.     update(u,v,val,id*2+1,mid+1,r);
  39.     st[id] = st[id*2] + st[id*2+1];
  40. }
  41. ll get(ll u, ll v,ll id=1,ll l=1, ll r=n)
  42. {
  43.     if (u > r || v < l) return 0;
  44.     if (u <= l && r <= v) return st[id];
  45.     ll mid = (l+r) >> 1;
  46.     down(id,l,r,mid);
  47.     return get(u,v,id*2,l,mid) + get(u,v,id*2+1,mid+1,r);
  48. }
  49.  
  50.  
  51. struct query
  52. {
  53.     ll l,r,c;
  54. }Q[maxn];
  55. bool cmp(query x, query y)
  56. {
  57.     return x.r < y.r;
  58. }
  59. main()
  60. {
  61.     ios_base::sync_with_stdio(false);
  62.     cin.tie(NULL);
  63.     cin >> n >> q;
  64.     for (int i=1;i<=q;i++) cin >> Q[i].l >> Q[i].r >> Q[i].c;
  65.     for (int i=1;i<=n;i++) dp[i] = 1e18;
  66.     dp[0] = 0;
  67.     sort(Q+1,Q+q+1,cmp);
  68.     for (auto p:Q)
  69.     {
  70.         ll l = p.l;
  71.         ll c = p.c;
  72.         ll r = p.r;
  73.         for (int i=l;i<=r;i++)
  74.         {
  75.             for (int j=l-1;j<=r-1;j++)
  76.             {
  77.                 dp[i] = min(dp[i],dp[j] + c);
  78.             }
  79.         }
  80.     }   
  81.     if (dp[n] != 1e18)    cout << dp[n];
  82.     else cout << -1;
  83.     return 0;
  84. }
Success #stdin #stdout 0.01s 5648KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ln59mp
language:
C++14 (gcc 8.3)
created:
2 days 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!