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 , m;
  22. pair<ll,ll> thoc[Maxn],th[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 Rutgon()
  54. {
  55.     n = 0 ;
  56.     for (int i = 1 ; i <= m ; ++i)
  57.     {
  58.         int j = i;
  59.         while(th[i].fi==th[j+1].fi)
  60.         {
  61.             j++;
  62.             th[i].se+=th[j].fi;
  63.         }
  64.         thoc[++n]=th[i];
  65.         i = j;
  66.     }
  67. }
  68.  
  69. void Do()
  70. {
  71.     cin >> m >> k;
  72.     for (int i = 1 ; i <= m ; ++i) cin >> th[i].fi;
  73.     for (int i = 1 ; i <= m ; ++i) cin >> th[i].se;
  74.     sort(th+1,th+1+m);
  75.     Rutgon();
  76.     for (int i = 1 ; i <= n ; ++i)
  77.     {
  78.         mul[i] = mul[i-1]+thoc[i].fi*thoc[i].se;
  79.         ps[i] = ps[i-1]+thoc[i].se;
  80.         //cout << mul[i] << ' ' << ps[i] << '\n';
  81.     }
  82.     ll l = 0 , r = 1e18;
  83.     while(l<=r)
  84.     {
  85.         ll mid = (l+r)/2;
  86.         //cerr << l << ' ' << mid << ' ' << r << ' ' ;
  87.         if(Check(mid))r=mid-1;
  88.         else l = mid+1;
  89.     }
  90.     cout << l;
  91. }
  92.  
  93. signed main ()
  94. {
  95.     ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  96. #define task "test"
  97.     if(fopen(task".inp", "r")){
  98.         freopen(task".inp", "r", stdin);
  99.         freopen(task".out", "w", stdout);
  100.     }
  101.     int ntest=1;
  102.     while(ntest--) Do();
  103.     cerr<<"\nTime elapsed: "<<1000*clock()/CLOCKS_PER_SEC<<"ms\n";
  104. }
  105.  
  106.  
Success #stdin #stdout #stderr 0.01s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Time elapsed: 7ms
https://ideone.com/b0n9cq
language:
C++14 (gcc 8.3)
created:
13 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!