fork download
copy 
  1. // ~~ icebear ~~
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef pair<int, int> ii;
  7. typedef pair<ii, int> iii;
  8.  
  9. #define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
  10. #define FORR(i,a,b) for(int i=(a); i>=(b); --i)
  11. #define rep(i, n) for(int i=0; i<(n); ++i)
  12. #define red(i, n) for(int i=(n)-1; i>=0; --i)
  13. #define mp make_pair
  14. #define pb push_back
  15. #define fi first
  16. #define se second
  17. #define all(x) x.begin(), x.end()
  18. #define task "icebearat"
  19.  
  20. const int MOD = 1e9 + 7;
  21. const int inf = 1e9 + 27092008;
  22. const ll LLinf = 1e18 + 27092008;
  23. const int N = 1e6 + 5;
  24. const int LG = 27;
  25. int n, k;
  26. int a[N], c[N];
  27. int rmq[N][LG];
  28. deque<int> dq;
  29. ll dp[N];
  30.  
  31. void push(int id) {
  32.     while(!dq.empty() && dp[dq.back()] >= dp[id]) dq.pop_back();
  33.     dq.pb(id);
  34. }
  35.  
  36. int get(int l, int r) {
  37.     int k = __lg(r - l + 1);
  38.     return (rmq[l][k] & rmq[r - (1 << k) + 1][k]);
  39. }
  40.  
  41. void solve() {
  42.     cin >> n >> k;
  43.     FOR(i,1,n) cin >> a[i];
  44.     FOR(i,1,n) cin >> c[i];
  45.     FOR(i,1,n) {
  46.         dp[i] = LLinf;
  47.         rmq[i][0] = a[i];
  48.     }
  49.     dq.clear();
  50.  
  51.     FOR(j,1,__lg(n))
  52.         FOR(i,1,n - (1<<j) + 1)  
  53.             rmq[i][j] = (rmq[i][j-1] & rmq[i + (1 << (j-1))][j-1]);
  54.  
  55.     dq.pb(0);
  56.     FOR(i,1,n) {
  57.         if (get(i, min(i+k-1, n)) == 0) dp[i] = dp[i-1];
  58.         if (!dq.empty() && dq.front() < i - k) dq.pop_front();
  59.         if (!dq.empty()) dp[i] = min(dp[i], c[i] + dp[dq.front()]);
  60.         push(i);
  61.     } 
  62.  
  63.     cout << *min_element(dp + n - k + 1, dp + n + 1) << '\n';
  64. }
  65.  
  66. int main() {
  67.     ios_base::sync_with_stdio(0);
  68.     cin.tie(0); cout.tie(0);
  69.     if (fopen(task".inp", "r")){
  70.         freopen(task".inp", "r", stdin);
  71.         freopen(task".out", "w", stdout);
  72.     }
  73.     int tc = 1;
  74.     cin >> tc;
  75.     while(tc--) solve();
  76.     return 0;
  77. }
  78.  
Success #stdin #stdout 0.01s 5600KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/4Qfapj
language:
C++ (gcc 8.3)
created:
3 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!