#include <bits/stdc++.h>
#define dbg(x) cerr << #x << " = " << x << "\n"
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie()
using namespace std;
using ll = long long;
char c[2000][2000];
bool cmp(pair <int, int> x, pair <int, int> y) {
return c[x.first][x.second] < c[y.first][y.second];
}
int main() {
fast_io;
int n, m;
cin >> n >> m;
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
cin >> c[i][j];
vector <pair <int, int> > p, np;
p.push_back(make_pair(0, 0));
for (int i = 0; i < n + m - 1; ++i) {
sort(p.begin(), p.end(), cmp);
cout << c[p[0].first][p[0].second];
if (i == n + m - 2)
break;
char ch = 'z';
for (auto j : p) {
int x = j.first, y = j.second;
if (x + 1 < n)
ch = min(ch, c[x + 1][y]);
if (y + 1 < m)
ch = min(ch, c[x][y + 1]);
}
for (auto j : p) {
int x = j.first, y = j.second;
if (x + 1 < n && c[x + 1][y] == ch)
np.push_back(make_pair(x + 1, y));
if (y + 1 < m && c[x][y + 1] == ch)
np.push_back(make_pair(x, y + 1));
}
p = np;
np.clear();
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
6 ms |
1408 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
8 ms |
1280 KB |
Output is correct |
7 |
Correct |
23 ms |
4352 KB |
Output is correct |
8 |
Correct |
57 ms |
8184 KB |
Output is correct |
9 |
Correct |
5 ms |
512 KB |
Output is correct |
10 |
Correct |
13 ms |
896 KB |
Output is correct |
11 |
Correct |
25 ms |
768 KB |
Output is correct |
12 |
Correct |
14 ms |
2560 KB |
Output is correct |
13 |
Correct |
13 ms |
4480 KB |
Output is correct |
14 |
Execution timed out |
1091 ms |
16208 KB |
Time limit exceeded |
15 |
Runtime error |
379 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
16 |
Runtime error |
410 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |