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 |
|
|
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 |