fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define N 1000000
  3. #define inf int(1e9+7)
  4. #define pii pair<int,int>
  5. #define pll pair<ll,ll>
  6. #define fi first
  7. #define se second
  8. #define pb push_back
  9. #define all(x) x.begin(),x.end()
  10. using namespace std;
  11. typedef long long ll;
  12. typedef double db;
  13. typedef pair<long long, int> li;
  14. typedef pair<long long, li> loli;
  15. // loli
  16. loli gspvhcute;
  17. //:333
  18.  
  19.  
  20. const int M = 1e9+7;
  21. int n,L;
  22. int h[N+3],w[N+3];
  23. deque<int> dq;
  24. ll dp[N+3];
  25. multiset<ll> ms;
  26.  
  27.  
  28. void Solve(){
  29.     int j = 1;
  30.     ll cur = 0;
  31.     for(int i=1; i<=n; i++){
  32.         cur += w[i];
  33.         while(cur > L){
  34.             cur -= w[j];
  35.             j++;
  36.         }
  37.  
  38.         while(!dq.empty() && dq.front() < j){
  39.             if(dq.size() >= 2)
  40.                 ms.erase(ms.find(dp[ dq[0] ] + h[dq[1]]));
  41.             dq.pop_front();
  42.         }
  43.         while(!dq.empty() && h[dq.back()] <= h[i]){
  44.             if(dq.size() >= 2)
  45.                 ms.erase(ms.find(dp[ dq[dq.size()-2] ] + h[dq.back()]));
  46.              dq.pop_back();
  47.         }
  48.  
  49.         if(!dq.empty())
  50.             ms.insert(dp[ dq.back() ] + h[i]);
  51.         dq.push_back(i);
  52.         dp[i] = dp[j-1] + h[dq.front()];
  53.         if(!ms.empty())
  54.             dp[i] = min(dp[i],*ms.begin());
  55.     }
  56.     cout << dp[n] << "\n";
  57.     ms.clear();
  58.     dq.clear();
  59. }
  60.  
  61. void Inp(){
  62.     cin >> n >> L;
  63.     for(int i=1; i<=n; i++){
  64.         cin >> h[i] >> w[i];
  65.     }
  66. }
  67.  
  68. int main(){
  69. 	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  70. 	freopen("BOOKS.inp","r",stdin);
  71. 	freopen("BOOKS.out","w",stdout);
  72. 	int T=1;
  73. 	cin >> T;
  74. 	while(T--){
  75. 	Inp();
  76. 	Solve();
  77. 	}
  78. }
  79. //-----YEU CODE HON CRUSH-----//
Success #stdin #stdout 0.01s 5920KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/aVJ3jx
language:
C++14 (gcc 8.3)
created:
4 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!