Submission #826334

#TimeUsernameProblemLanguageResultExecution timeMemory
826334ajayPohlepko (COCI16_pohlepko)C++14
10 / 80
1087 ms41472 KiB
/* Ajay Jadhav */ #include <iostream> #include <cstdio> #include <algorithm> #include <deque> #include <vector> #include <cstdlib> #include <iomanip> #include <cmath> #include <queue> #include <map> #include <set> #include <stack> #include <ctime> #include <string.h> #include <climits> #include <cstring> using namespace std; #define ll long long #define pb push_back #define pii pair<int, int> #define vi vector<int> #define vvi vector<vi> #define vii vector<pii> #define mi map<int, int> #define mii map<pii, int> #define all(a) (a).begin(), (a).end() #define x first #define y second #define sz(x) (int)x.size() #define hell 1000000007 #define rep(i, a, b) for (int i = a; i < b; i++) #define endl '\n' string ans; void trace_direction(vector<string> &g, vector<vector<char>> &dir, int i, int j, string tmp) { if (i < 0 or j < 0) { reverse(all(tmp)); if (ans == "") ans = tmp; else ans = min(ans, tmp); return; } if (dir[i][j] == 'b') { trace_direction(g, dir, i - 1, j, tmp + g[i][j]); trace_direction(g, dir, i, j - 1, tmp + g[i][j]); } else if (dir[i][j] == 'l') { trace_direction(g, dir, i, j - 1, tmp + g[i][j]); } else { trace_direction(g, dir, i - 1, j, tmp + g[i][j]); } } void solve() { int n, m; cin >> n >> m; vector<string> g(n); rep(i, 0, n) { cin >> g[i]; } vvi dp(n, vi(m, 0)); vector<vector<char>> dir(n, vector<char>(m, 'x')); dp[0][0] = (g[0][0] - 'a'); dir[0][0] = 'u'; rep(i, 1, n) { dp[i][0] = dp[i - 1][0] + (g[i][0] - 'a'); dir[i][0] = 'u'; } rep(i, 1, m) { dp[0][i] = dp[0][i - 1] + (g[0][i] - 'a'); dir[0][i] = 'l'; } rep(i, 1, n) { rep(j, 1, m) { if (dp[i - 1][j] == dp[i][j - 1]) { dp[i][j] += dp[i - 1][j] + (g[i][j] - 'a'); dir[i][j] = 'b'; } else if (dp[i - 1][j] < dp[i][j - 1]) { dp[i][j] += dp[i - 1][j] + (g[i][j] - 'a'); dir[i][j] = 'u'; } else { dp[i][j] += dp[i][j - 1] + (g[i][j] - 'a'); dir[i][j] = 'l'; } } } int i = n - 1, j = m - 1; trace_direction(g, dir, n - 1, m - 1, ""); cout << ans << endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t = 1; // cin>>t; while (t--) { solve(); } return 0; }

Compilation message (stderr)

pohlepko.cpp: In function 'void solve()':
pohlepko.cpp:115:9: warning: unused variable 'i' [-Wunused-variable]
  115 |     int i = n - 1, j = m - 1;
      |         ^
pohlepko.cpp:115:20: warning: unused variable 'j' [-Wunused-variable]
  115 |     int i = n - 1, j = m - 1;
      |                    ^
#Verdict Execution timeMemoryGrader output
Fetching results...