Submission #1156003


Source Code Expand

#include <iostream>
#include <vector>

using namespace std;

template<typename T>
vector<vector<T>> make_2d_vector(size_t rows, size_t cols, T init)
{ return vector< vector<T> >(rows, vector<T>(cols, init)); }



#define debug(x) cout << #x << "==" << x << endl;

const int inf = 100000000;

typedef long long ll;

int main() {
  ios::sync_with_stdio(false);

  int N;
  cin >> N;

  auto tri = make_2d_vector(N, N, inf);
  for(int i = 0; i < N; i++) {
    for(int j = 0; j <= i; j++) {
      cin >> tri[i][j];
    }
  }

  // 貰うDP
  // auto dp = make_2d_vector(N, N, 0);
  // dp[0][0] = tri[0][0];
  // for(int i = 1; i < N; i++ ) {
  //   for(int j = 0; j <= i; j++) {

  //     if( j == 0 )
  //       dp[i][j] = dp[i-1][j];
  //     else
  //       dp[i][j] = max( dp[i-1][j], dp[i-1][j-1] );

  //     dp[i][j] += tri[i][j];

  //   }
  // }

  // 配るDP
  auto dp = make_2d_vector(N, N, 0);
  for(int i = 0; i < N; i++ ) {
    for(int j = 0; j <= i; j++) {

      dp[i][j] += tri[i][j];

      if( i != N-1 ) {
        dp[i+1][j]   = max(   dp[i+1][j], dp[i][j] );
        dp[i+1][j+1] = dp[i][j];
      }

    }
  }


  int res = 0;
  for(int i = 0; i < N; i++) {
    res = max(res, dp[N-1][i]);
  }
  cout << res << "\n";


  return 0;

}

Submission Info

Submission Time
Task D - 三角パズル
User sadtomato
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1325 Byte
Status AC
Exec Time 1 ms
Memory 256 KB

Judge Result

Set Name sub1 sub2
Score / Max Score 50 / 50 50 / 50
Status
AC × 13
AC × 24
Set Name Test Cases
sub1 sub1/input_0.txt, sub1/input_1.txt, sub1/input_14.txt, sub1/input_15.txt, sub1/input_18.txt, sub1/input_19.txt, sub1/input_2.txt, sub1/input_20.txt, sub1/input_3.txt, sub1/input_4.txt, sub1/input_5.txt, sub1/input_6.txt, sub1/input_9.txt
sub2 sub2/input_0.txt, sub2/input_1.txt, sub2/input_10.txt, sub2/input_11.txt, sub2/input_12.txt, sub2/input_13.txt, sub2/input_14.txt, sub2/input_15.txt, sub2/input_16.txt, sub2/input_17.txt, sub2/input_18.txt, sub2/input_19.txt, sub2/input_2.txt, sub2/input_20.txt, sub2/input_21.txt, sub2/input_22.txt, sub2/input_23.txt, sub2/input_3.txt, sub2/input_4.txt, sub2/input_5.txt, sub2/input_6.txt, sub2/input_7.txt, sub2/input_8.txt, sub2/input_9.txt
Case Name Status Exec Time Memory
sub1/input_0.txt AC 1 ms 256 KB
sub1/input_1.txt AC 1 ms 256 KB
sub1/input_14.txt AC 1 ms 256 KB
sub1/input_15.txt AC 1 ms 256 KB
sub1/input_18.txt AC 1 ms 256 KB
sub1/input_19.txt AC 1 ms 256 KB
sub1/input_2.txt AC 1 ms 256 KB
sub1/input_20.txt AC 1 ms 256 KB
sub1/input_3.txt AC 1 ms 256 KB
sub1/input_4.txt AC 1 ms 256 KB
sub1/input_5.txt AC 1 ms 256 KB
sub1/input_6.txt AC 1 ms 256 KB
sub1/input_9.txt AC 1 ms 256 KB
sub2/input_0.txt AC 1 ms 256 KB
sub2/input_1.txt AC 1 ms 256 KB
sub2/input_10.txt AC 1 ms 256 KB
sub2/input_11.txt AC 1 ms 256 KB
sub2/input_12.txt AC 1 ms 256 KB
sub2/input_13.txt AC 1 ms 256 KB
sub2/input_14.txt AC 1 ms 256 KB
sub2/input_15.txt AC 1 ms 256 KB
sub2/input_16.txt AC 1 ms 256 KB
sub2/input_17.txt AC 1 ms 256 KB
sub2/input_18.txt AC 1 ms 256 KB
sub2/input_19.txt AC 1 ms 256 KB
sub2/input_2.txt AC 1 ms 256 KB
sub2/input_20.txt AC 1 ms 256 KB
sub2/input_21.txt AC 1 ms 256 KB
sub2/input_22.txt AC 1 ms 256 KB
sub2/input_23.txt AC 1 ms 256 KB
sub2/input_3.txt AC 1 ms 256 KB
sub2/input_4.txt AC 1 ms 256 KB
sub2/input_5.txt AC 1 ms 256 KB
sub2/input_6.txt AC 1 ms 256 KB
sub2/input_7.txt AC 1 ms 256 KB
sub2/input_8.txt AC 1 ms 256 KB
sub2/input_9.txt AC 1 ms 256 KB