MinhNGUYEN2k4

wifi

Feb 19th, 2021 (edited)
160
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.46 KB | None | 0 0
  1. //Nguyen Huu Hoang Minh
  2. #include <bits/stdc++.h>
  3. #define sz(x) int(x.size())
  4. #define all(x) x.begin(),x.end()
  5. #define reset(x) memset(x, 0,sizeof(x))
  6. #define pb push_back
  7. #define mp make_pair
  8. #define fi first
  9. #define se second
  10. #define N 1000005
  11. #define remain(x) if (x > MOD) x -= MOD
  12. #define ii pair<int, int>
  13. #define iiii pair< ii , ii >
  14. #define viiii vector< iiii >
  15. #define vi vector<int>
  16. #define vii vector< ii >
  17. #define bit(x, i) (((x) >> (i)) & 1)
  18. #define Task "test"
  19. #define int long long
  20.  
  21. using namespace std;
  22.  
  23. typedef long double ld;
  24. const int inf = 1e10;
  25. const int minf = -1e10;
  26.  
  27. int n, k, a[N], val[N], f[N];
  28.  
  29. void readfile()
  30. {
  31.     ios_base::sync_with_stdio(false);
  32.     cin.tie(0);cout.tie(0);
  33.     if (fopen(Task".inp","r"))
  34.     {
  35.         freopen(Task".inp","r",stdin);
  36.         //freopen(Task".out","w",stdout);
  37.     }
  38.     cin >> n >> k;
  39.     for(int i=1; i<=n; i++) cin >> a[i];
  40.     for(int i=1; i<=n; i++) cin >> val[i];
  41. }
  42.  
  43. int bs(int l, int r, int val)
  44. {
  45.     int mid = (l + r)/2;
  46.     if (l == r) return l;
  47.     if (r - l == 1)
  48.     {
  49.         if (a[r] <= val) return r;
  50.         return l;
  51.     }
  52.     if (a[mid] <= val) return bs(mid,r,val);
  53.     return bs(l,mid,val);
  54. }
  55.  
  56. void proc()
  57. {
  58.     a[0] = -9999;
  59.     f[0] = 0;
  60.     for(int i=1; i<=n; i++)
  61.     {
  62.         f[i] = val[i];
  63.         int j = bs(0,i-1,a[i]-k);
  64.         f[i] += f[j];
  65.     }
  66.     cout << f[n];
  67. }
  68.  
  69. signed main()
  70. {
  71.     readfile();
  72.     proc();
  73.     return 0;
  74. }
  75.  
Add Comment
Please, Sign In to add comment