YEZAELP

CUBE-119: COI Road Cube

Oct 24th, 2020 (edited)
114
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.21 KB | None
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. struct Data{
  5.     int val;
  6.     int idx;
  7. };
  8. const int N = 1e2 + 10;
  9. const int M = 1e4 + 10;
  10. int dp[N][M], ar[N][M];
  11.  
  12. int main(){
  13.  
  14.     int n, m, k;
  15.     scanf("%d%d%d", &n, &m, &k);
  16.  
  17.     for(int j = 1; j <= m; j++){
  18.         scanf("%d", &ar[1][j]);
  19.         dp[1][j] = ar[1][j];
  20.     }
  21.  
  22.     for(int i = 2; i <= n; i++){
  23.         for(int j = 1; j <= m; j++) {
  24.             scanf("%d", &ar[i][j]);
  25.         }
  26.         deque <Data> dq;
  27.  
  28.         for(int j = 1; j <= min(k + 1, m); j++){
  29.             while(!dq.empty() and dq.back().val <= dp[i-1][j])
  30.                 dq.pop_back();
  31.             dq.push_back({dp[i-1][j], j});
  32.         }
  33.         dp[i][1] = dq.front().val + ar[i][1];
  34.  
  35.         for(int j = 2; j <= m; j++){
  36.             while(!dq.empty() and j - dq.front().idx > k)
  37.                 dq.pop_front();
  38.             while(j + k <= m and !dq.empty() and dq.back().val <= dp[i-1][j+k])
  39.                 dq.pop_back();
  40.             dq.push_back({dp[i-1][j+k], j + k});
  41.             dp[i][j] = dq.front().val + ar[i][j];
  42.         }
  43.     }
  44.  
  45.     int mx = 0;
  46.     for(int j = 1;j <= m; j++)
  47.         mx = max(mx, dp[n][j]);
  48.     printf("%d", mx);
  49.  
  50.     return 0;
  51. }
RAW Paste Data Copied