Submission #4243171


Source Code Expand

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <unordered_map>
#include <vector>
using namespace std;

#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()

const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
/*----------------------------------------*/
int main() {
  cin.tie(0); ios::sync_with_stdio(false);
  // freopen("input.txt", "r", stdin);

  int n; cin >> n;
  vector<vector<int> > a(n, vector<int>(n, -INF)); REP(i, n) REP(j, i+1) cin >> a[i][j];
  vector<vector<int> > dp(n, vector<int>(n, 0));
  dp[0][0] = a[0][0];
  FOR(i, 1, n) {
    dp[i][0] = dp[i-1][0] + a[i][0];
    FOR(j, 1, i+1) dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + a[i][j];
  }
  int ans = 0;
  REP(i, n) ans = max(ans, dp[n-1][i]);
  cout << ans << '\n';
  return 0;
}

Submission Info

Submission Time
Task D - 三角パズル
User emthrm
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1179 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