fork download
copy 
  1. // SIGMA BOY hihihihihihihi
  2.  
  3. #define se second
  4. #define fi first
  5. #define pb push_back
  6. #define pob pop_back
  7. #define bitebi __builtin_popcountll
  8. #include <bits/stdc++.h>
  9.  
  10. using namespace std ;
  11. typedef long long ll;
  12. typedef long double ld;
  13. typedef pair<ll,ll> pll;
  14. typedef pair<int,int> pii;
  15. const ll Mod = 1e9+7;
  16. const ll Maxn = 1e6+69;
  17. const ll Maxm = 3e3+69;
  18. const ll oo = 1e18;
  19. const int inf = 1e9;
  20.  
  21. ll n , k ;
  22. pair<ll,ll> thoc[Maxn];
  23. ll mul[Maxn],ps[Maxn];
  24.  
  25. bool Cal ( ll id1 , ll &idbf , ll &location, ll id2 , ll timecheck)
  26. {
  27.     while(location<=thoc[id2].fi)
  28.     {
  29.         ll time = location*(2*ps[idbf]-ps[id1-1]-ps[id2])-2*mul[idbf]+mul[id1-1]+mul[id2];
  30.         //cerr << time << ' ' << id1 << ' ' << id2 << ' ' << idbf << ' '  << location << '\n' ;
  31.         if(time <= timecheck) return true;
  32.         location++;
  33.         if(idbf+1<=n&&location>=thoc[idbf+1].fi)idbf++;
  34.     }
  35.     return false;
  36. }
  37.  
  38. bool Check ( ll t )
  39. {
  40.     ll slot = 0 ;
  41.     for (ll i = 1 ; i <= n ; ++i)
  42.     {
  43.         ll j = i , location = thoc[i].fi , idthoctrcloc = i ;
  44.         while(i<n&&Cal(j,idthoctrcloc,location,i+1,t))i++;
  45.         //cerr << i << ' ' << location << '\n';
  46.         slot++;
  47.     }
  48.     //cerr << slot << '\n' << '\n' << '\n';
  49.     if(slot<=k) return true;
  50.     return false;
  51. }
  52.  
  53. void Do()
  54. {
  55.     cin >> n >> k;
  56.     for (int i = 1 ; i <= n ; ++i) cin >> thoc[i].fi;
  57.     for (int i = 1 ; i <= n ; ++i) cin >> thoc[i].se;
  58.     sort(thoc+1,thoc+1+n);
  59.  
  60.     for (int i = 1 ; i <= n ; ++i)
  61.     {
  62.         mul[i] = mul[i-1]+thoc[i].fi*thoc[i].se;
  63.         ps[i] = ps[i-1]+thoc[i].se;
  64.         //cout << mul[i] << ' ' << ps[i] << '\n';
  65.     }
  66.     ll l = 0 , r = 1e18;
  67.     while(l<=r)
  68.     {
  69.         ll mid = (l+r)/2;
  70.         //cerr << l << ' ' << mid << ' ' << r << ' ' ;
  71.         if(Check(mid))r=mid-1;
  72.         else l = mid+1;
  73.     }
  74.     cout << l;
  75. }
  76.  
  77. signed main ()
  78. {
  79.     ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  80. #define task "test"
  81.     if(fopen(task".inp", "r")){
  82.         freopen(task".inp", "r", stdin);
  83.         freopen(task".out", "w", stdout);
  84.     }
  85.     int ntest=1;
  86.     while(ntest--) Do();
  87.     cerr<<"\nTime elapsed: "<<1000*clock()/CLOCKS_PER_SEC<<"ms\n";
  88. }
  89.  
Success #stdin #stdout #stderr 0.01s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Time elapsed: 5ms
https://ideone.com/2iY6mZ
language:
C++14 (gcc 8.3)
created:
12 hours 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!