fork(11) download 
  1. #include <cstdio>
  2. #include <climits>
  3. #include <deque>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. typedef long long lint;
  9.  
  10. int main()
  11. {
  12.     int N, M, D;
  13.     int a[1000], b[1000], t[1000];
  14.     lint dp[2][300001];
  15.  
  16.     scanf("%d %d %d", &N, &M, &D);
  17.  
  18.     for (int i = 0; i < M; i++){
  19.         scanf("%d %d %d", a + i, b + i, t + i);
  20.     }
  21.  
  22.     for (int i = 1; i <= N; i++){
  23.         dp[0][i] = 0;
  24.     }
  25.  
  26.     int p = 1;
  27.     int pT = 1;
  28.     for (int i = 0; i < M; i++){
  29.         deque<int> dq;
  30.         lint interval = min((lint)N, (lint)(t[i] - pT) * D);
  31.  
  32.         for (lint j = 1; j <= interval; j++){
  33.             while (dq.size() && dp[1 - p][dq[dq.size() - 1]] <= dp[1 - p][(int)j]) dq.pop_back();
  34.             dq.push_back((int)j);
  35.         }
  36.  
  37.         for (lint j = 1; j <= (lint)N; j++){
  38.             lint k = j + interval;
  39.             if (k <= (lint)N){
  40.                 while (dq.size() && dp[1 - p][dq[dq.size() - 1]] <= dp[1 - p][(int)k]) dq.pop_back();
  41.                 dq.push_back((int)k);
  42.             }
  43.             dp[p][j] = dp[1 - p][dq[0]] + (lint)(b[i] - abs(a[i] - j));
  44.             while (dq.size() && dq[0] <= (int)(j - interval)) dq.pop_front();
  45.         }
  46.         pT = t[i];
  47.         p = 1 - p;
  48.     }
  49.  
  50.     lint ans = LLONG_MIN;
  51.     for (int i = 1; i <= N; i++)
  52.         ans = max(ans, dp[1 - p][i]);
  53.  
  54.     printf("%I64d\n", ans);
  55.  
  56.     return (0);
  57. }
Success #stdin #stdout 0s 7928KB
comments (?)
stdin 
Standard input is empty
stdout 
                                                               0
https://ideone.com/Unrfaa
language:
C++ (gcc 8.3)
created:
10 years 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!