Advertisement
mickypinata

USACO-T018: Number Triangles

Nov 28th, 2021
638
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. ID: mickyta1
  3. TASK: numtri
  4. LANG: C++
  5. */
  6.  
  7. #include <bits/stdc++.h>
  8. using namespace std;
  9.  
  10. const int N = 1000 + 5;
  11.  
  12. int arr[N][N], dp[2][N];
  13.  
  14. int main(){
  15.     freopen("numtri.in", "r", stdin);
  16.     freopen("numtri.out", "w", stdout);
  17.  
  18.     int n;
  19.     scanf("%d", &n);
  20.     for(int i = 1; i <= n; ++i){
  21.         for(int j = 1; j <= i; ++j){
  22.             scanf("%d", &arr[i][j]);
  23.         }
  24.     }
  25.     for(int i = n; i >= 1; --i){
  26.         int cur = i % 2;
  27.         int nxt = cur ^ 1;
  28.         for(int j = 1; j <= n; ++j){
  29.             dp[cur][j] = arr[i][j] + max(dp[nxt][j], dp[nxt][j + 1]);
  30.         }
  31.     }
  32.     cout << dp[1][1] << '\n';
  33.  
  34.     fclose(stdin);
  35.     fclose(stdout);
  36.     return 0;
  37. }
  38.  
Advertisement
RAW Paste Data Copied
Advertisement