Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define IOS ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
- #define X first
- #define Y second
- #define Push push_back
- #define ALL(x) x.begin(), x.end()
- using lli = long long;
- using pll = pair<lli, lli>;
- using Double = long double;
- template<typename T>
- using Vector = vector<vector<T>>;
- template<typename T>
- using prior = priority_queue<T>;
- int main() {
- IOS;
- int n;
- cin >> n;
- Vector<int> mp(n + 1, vector<int>(n + 1, 0));
- for (int i = 1; i <= n; ++i) {
- for (int j = 1; j <= i; ++j) {
- cin >> mp[i][j];
- }
- }
- Vector<pll> dp(n + 1, vector<pll>(n + 1, {0, 0}));
- dp[1][1].X = mp[1][1];
- for (int i = 1; i <= n; ++i) {
- for (int j = 1; j <= i; ++j) {
- dp[i][j].X = max(dp[i][j - 1].X, dp[i - 1][j].X) + mp[i][j];
- if (dp[i][j - 1].X > dp[i - 1][j].X) dp[i][j].Y = 0; // east
- else dp[i][j].Y = 1; // south
- }
- }
- string walk = "E";
- int x = n, y = n;
- while (x > 1 or y > 1) {
- if (dp[x][y].Y) {
- walk += 'S';
- --x;
- }
- else {
- walk += 'E';
- --y;
- }
- }
- walk += "E";
- reverse(ALL(walk));
- cout << walk << "\n";
- cout << dp[n][n].X << "\n";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement