Advertisement
Guest User

Which Line?

a guest
Nov 18th, 2019
95
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.77 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int vals[300000][2];
  6. int memo[300000][2];
  7. long long ans;
  8.  
  9. long long solve(int n, int k) {
  10.     // compute and solve answer here
  11.     for(int i = 0; i < n; i++) {
  12.         for(int j = 0; j < 2; j++) {
  13.             ans = 0;
  14.             if (i == 0) {
  15.                 ans = vals[i][j];
  16.             }
  17.             else {
  18.                 ans = vals[i][j] + min(memo[i - 1][j], k + memo[i - 1][1 - j]);
  19.             }
  20.             memo[i][j] = ans;
  21.         }
  22.     }  
  23.     return min(memo[n - 1][0], memo[n - 1][1]);
  24. }
  25.  
  26. int main() {
  27.     int n, k, i, j;
  28.     cin >> n >> k;
  29.     for(i = 0; i < n; i++) {
  30.         for(j = 0; j < 2; j++) {
  31.             // use scanf to avoid TLE
  32.             scanf("%d",&vals[i][j]);
  33.         }
  34.     }
  35.    
  36.     cout << solve(n,k) << endl;
  37. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement