fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const int N = 500005;
  5. const long long maxf=1e15;
  6. int n;
  7. int p[N], t[N];
  8. long long f[N], a[N*4];
  9.  
  10. void read_file()
  11. {
  12.     cin>>n;
  13.     for (int i=1;i<=n;i++)
  14.     {
  15.         cin>>t[i]>>p[i];
  16.     }
  17. }
  18.  
  19. void update(int id, int l, int r, int i, long long v) {
  20.     if (i < l || r < i) {
  21.         return ;
  22.     }
  23.     if (l == r) {
  24.         a[id] = v;
  25.         return ;
  26.     }
  27.  
  28.     int mid = (l + r) / 2;
  29.     update(id*2, l, mid, i, v);
  30.     update(id*2 + 1, mid+1, r, i, v);
  31.     a[id] = min(a[id*2], a[id*2 + 1]);
  32. }
  33.  
  34. long long getmin(int id, int l, int r, int u, int v) {
  35.     if (v < l || r < u) {
  36.         return maxf;
  37.     }
  38.     if (u <= l && r <= v) {
  39.         return a[id];
  40.     }
  41.     int mid = (l + r) / 2;
  42.     return min(getmin(id*2, l, mid, u, v), getmin(id*2 + 1, mid+1, r, u, v));
  43. }
  44.  
  45.  
  46. void solve()
  47. {
  48.     long long v;
  49.     for (int i=1;i<=n*4;i++) a[i]=maxf;
  50.     update(1,1,n,n,p[n]);
  51.     f[n]=p[n];
  52.     for (int i=n-1;i>0;i--)
  53.     {
  54.         v=0;
  55.         if (t[i]<n) v=getmin(1,1,n,i+1,t[i]+1);
  56.         f[i]=p[i]+v;
  57.         update(1,1,n,i,f[i]);
  58.     }
  59.     //for (int i=1;i<=n;i++) cout<<f[i]<<"\n";
  60. }
  61.  
  62. void solve2()
  63. {
  64.     f[n]=p[n];
  65.     for (int i=n-1;i>0;i--)
  66.     {
  67.         f[i]=p[i]+f[i+1];
  68.         for (int j=i+1;j<=t[i]+1;j++)
  69.         {
  70.             if (f[i]>f[j]+p[i])
  71.             {
  72.                 f[i]=f[j]+p[i];
  73.             }
  74.         }
  75.  
  76.     }
  77. }
  78.  
  79. void write_file()
  80. {
  81.     cout<<f[1];
  82. }
  83. int main()
  84. {
  85.     ios::sync_with_stdio(0);
  86.     cin.tie(0);cout.tie(0);
  87.     freopen("Holiday.inp","r",stdin);
  88.     freopen("Holiday.out","w",stdout);
  89.     read_file();
  90.     solve();
  91.     write_file();
  92. }
  93.  
  94.  
Success #stdin #stdout 0.01s 5968KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/08Zp3Z
language:
C++14 (gcc 8.3)
created:
1 year 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!