Ledger Nano X - The secure hardware wallet
SHARE
TWEET

Untitled

a guest Sep 30th, 2016 56 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /* Author haleyk10198 */
  2. /* 作者:  haleyk10198 */
  3. #include <bits/stdc++.h>
  4. #include <ext/pb_ds/assoc_container.hpp>
  5. #include <ext/pb_ds/tree_policy.hpp>
  6.  
  7. #define MOD 1000000007
  8. #define LINF (1LL<<60)
  9. #define INF 2147483647
  10. #define PI 3.1415926535897932384626433
  11. #define ll long long
  12. #define pii pair<int,int>
  13. #define mp(x,y) make_pair((x),(y))
  14.  
  15. using namespace std;
  16. using namespace __gnu_pbds;
  17.  
  18. string itos(int x){
  19.     stringstream ss;
  20.     ss<<x;
  21.     return ss.str();
  22. }
  23.  
  24. //GREEDY?! NOT DP?! NO WAY, JUST WAITING FOR PRESTEST KO.
  25. //OK FFS IF I GOT SLAMMED DOWN CUZ FORGOT TO HANDLE <0 ... I... I...
  26.  
  27. //OH GOSH EXCEPTIONS EXCEPTIONS EXCEPTIONS
  28.  
  29. int len,n,p,t,cur,res,mx;
  30.  
  31. map<int,int> dp;
  32.  
  33. int main(){
  34.     //freopen("input.txt","r",stdin);
  35.     //freopen("output.txt","w",stdout);
  36.     ios_base::sync_with_stdio(false);
  37.     cin>>len>>n>>p>>t;
  38.     dp[0]=0;
  39.     for(int i=0,l,r;i<n;i++){
  40.         cin>>l>>r;
  41.         cur=dp.rbegin()->first;
  42.         int tmp=dp[cur];
  43.         cur=max(l,cur);
  44.         tmp+=(r-cur)/p;
  45.         cur=r-(r-cur)%p;
  46.         if(--dp.upper_bound(cur+t)->second<tmp)
  47.             dp[cur+t]=tmp;
  48.         if(l-t<0)
  49.             tmp=0;
  50.         else
  51.             tmp=--dp.upper_bound(l-t)->second;
  52.         r-=(r-l)%p;
  53.         tmp+=(r-l)/p;
  54.         if((--dp.upper_bound(r+t))->second<tmp)
  55.             dp[r+t]=tmp;
  56.     }
  57.     cout<<(dp.rbegin()->second)<<endl;
  58.     return 0;
  59. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top