fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. using namespace std;
  4. const long long oo = 1e18;
  5. const long long N = 3003;
  6.  
  7. ll dp[N][N], a[3003], b[3003], c[3003], n, ans = oo;
  8.  
  9. void minimize(ll &a, ll b){
  10.     if (a > b) a = b;
  11. }
  12.  
  13.  
  14. int main(){
  15.  
  16.     ios_base::sync_with_stdio(0);
  17.     cin.tie(0); cout.tie(0);
  18.  
  19.     cin >> n;
  20.  
  21.     for (int i = 1; i <= n; i ++)
  22.         cin >> a[i] >> b[i] >> c[i];
  23.  
  24.     for (int i = 0; i <= n; i ++)
  25.         for (int j = 0; j <= n;j ++)
  26.                 dp[i][j] = oo;
  27.  
  28.     dp[0][0] = 0;
  29.  
  30.     for (int i = 0; i <= n; i ++)
  31.         for (int j = 0; j <= n; j ++)
  32.             if (i + j <= n)
  33.             {
  34.  
  35.                 ll idx = i + j;
  36.  
  37.                 if (j)
  38.                     minimize(dp[i][j], dp[i][j-1] + b[idx] - j + 1);
  39.                 if (i)
  40.                     minimize(dp[i][j], dp[i-1][j] + c[idx] - i + 1);
  41.  
  42.                 if (i + j == n)
  43.                     minimize(ans, dp[i][j]);
  44.             }
  45.  
  46.     cout << ans;
  47.  
  48. }
  49.  
  50.  
  51.  
Success #stdin #stdout 0.01s 5304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/jCd0eq
language:
C++14 (gcc 8.3)
created:
3 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!