fork download 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. using namespace std;
  4. const ll N=1e6 + 8;
  5. const int maxn = 2e5;
  6. ll t, aux;
  7. ll slope[N]={0}, c[N]={0};
  8. ll f(ll a, ll b, ll x)
  9. { return a*x+b;}
  10. void add_line(ll ms, ll con, int v = 1, ll l = 0, ll r = N/4) {
  11.     ll m= l + (r-l)/2;
  12.     bool lef = f(ms,con,l) < f(slope[v],c[v],l);
  13.     bool mid = f(ms,con,m) < f(slope[v],c[v],m);
  14.     if(mid) {
  15.         swap(slope[v], ms);
  16.         swap(c[v],con);
  17.     }
  18.     if(r - l == 1) {
  19.         return;
  20.     } else if(lef != mid) {
  21.         add_line(ms, con, 2 * v, l, m);
  22.     } else {
  23.         add_line(ms,con, 2 * v + 1, m, r);
  24.     }
  25. }
  26. ll get(ll x, int v = 1, ll l = 0, ll r = N/4) {
  27.     ll m = l + (r-l) / 2;
  28.     if(r - l == 1) 
  29.     { 
  30.     t=slope [v];
  31.       return f(slope[v],c[v],x);
  32.     }
  33.     else if(x>m) {
  34.     	    aux= get(x, 2 * v, l, m);
  35.          if (f(slope[v],c[v],x)>=aux)
  36.          {t=slope[v];
  37.          	return f(slope[v],c[v],x);        }         	
  38.     } else { 
  39.     	aux= get(x, 2 * v + 1, m, r);
  40. if(f(slope[v], c[v], x)> aux)
  41.        {
  42.    	t=slope [v];
  43.      return f(slope[v], c[v], x);
  44.         }
  45.     }
  46.     return aux;
  47. }
  48. int n;
  49. long long a[N], d[N];
  50. void load() {
  51.     scanf("%d", &n);
  52.     for (int i = 1; i <=n; ++i) {
  53.         scanf("%lld%lld", &a[i], &d[i]);
  54.     }
  55. }
  56. void process() {
  57.     long long cost = a[1];
  58.     add_line(-d[1], a[1]+d[1]);
  59. for (ll i = 2; i <= n; ++i) 
  60.            {
  61.         cost = a[i]+get(i);
  62.            if (i<n)
  63.         add_line(-d[i], cost+i*d[i]); 
  64.                }
  65.     printf("%lld",cost+t);
  66. }
  67. int main() {  
  68.         load();
  69.         process();
  70.       return 0;
  71. }
  72.  
Success #stdin #stdout 0s 46480KB
comments ()
stdin 
5
2 3
10 2
0 1
5 4
1 10
stdout 
5
https://ideone.com/2GfBzk
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!