#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
typedef pair<int, int> pi;
typedef long long int lint;
const int inf = 0x3f3f3f3f;
const int maxn = 2000 + 5;
int n, m;
char a[maxn][maxn];
char dp[maxn][maxn];
pair<int, int> src[maxn][maxn];
string rjesenje;
pair<char, char> fuki(int x1, int y1, int x2, int y2) {
while(a[x1][y1] == a[x2][y2]) {
tie(x1, y1) = src[x1][y1];
tie(x2, y2) = src[x2][y2];
if(x1 == -1 or x2 == -1)
return mp(0, 0);
}
return mp(a[x1][y1], a[x2][y2]);
}
int main ()
{
ios::sync_with_stdio(0);
cin >> n >> m;
for(int i = 0; i < n; ++i)
for(int j = 0; j < m; ++j)
cin >> a[i][j];
dp[0][0] = a[0][0];
src[0][0] = mp(-1, -1);
for(int i = 1; i < m; ++i) {
if(a[0][i] <= dp[0][i - 1]) {
src[0][i] = mp(-1, -1);
dp[0][i] = a[0][i];
} else {
src[0][i] = mp(0, i - 1);
dp[0][i] = dp[0][i - 1];
}
}
for(int i = 1; i < n; ++i) {
if(a[i][0] <= dp[i - 1][0]) {
src[i][0] = mp(-1, -1);
dp[i][0] = a[i][0];
} else {
src[i][0] = mp(i - 1, 0);
dp[i][0] = dp[i - 1][0];
}
dp[i][0] = min(a[i][0], dp[i - 1][0]);
}
for(int i = 1; i < n; ++i) {
for(int j = 1; j < m; ++j) {
if(dp[i][j - 1] < dp[i - 1][j]) {
dp[i][j] = dp[i][j - 1];
src[i][j] = mp(i, j - 1);
} else if(dp[i - 1][j] < dp[i][j - 1]) {
dp[i][j] = dp[i - 1][j];
src[i][j] = mp(i - 1, j);
} else if(dp[i - 1][j] == dp[i][j- 1]) {
char t1, t2;
tie(t1, t2) = fuki(i - 1, j, i, j - 1);
if(t1 == t2) {
dp[i][j] = dp[i - 1][j];
src[i][j] = mp(i - 1, j);
} else if(t1 < t2){
dp[i][j] = t1;
src[i][j] = mp(i - 1, j);
} else {
dp[i][j] = t2;
src[i][j] = mp(i, j - 1);
}
}
}
}
int curx = n - 1, cury = m - 1;
while(curx != -1) {
rjesenje.pb(a[curx][cury]);
tie(curx, cury) = src[curx][cury];
}
for(int i = rjesenje.size() - 1; i >= 0; --i)
cout << rjesenje[i];
return 0;
}
//written and directed by pcelicamaja
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
4352 KB |
Output isn't correct |
| 3 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 4 |
Incorrect |
2 ms |
768 KB |
Output isn't correct |
| 5 |
Incorrect |
3 ms |
512 KB |
Output isn't correct |
| 6 |
Incorrect |
15 ms |
5248 KB |
Output isn't correct |
| 7 |
Incorrect |
56 ms |
22776 KB |
Output isn't correct |
| 8 |
Incorrect |
148 ms |
43624 KB |
Output isn't correct |
| 9 |
Incorrect |
3 ms |
1152 KB |
Output isn't correct |
| 10 |
Incorrect |
6 ms |
2560 KB |
Output isn't correct |
| 11 |
Incorrect |
8 ms |
2432 KB |
Output isn't correct |
| 12 |
Incorrect |
27 ms |
11264 KB |
Output isn't correct |
| 13 |
Incorrect |
23 ms |
17912 KB |
Output isn't correct |
| 14 |
Execution timed out |
1080 ms |
35972 KB |
Time limit exceeded |
| 15 |
Incorrect |
9 ms |
1280 KB |
Output isn't correct |
| 16 |
Execution timed out |
1068 ms |
17372 KB |
Time limit exceeded |
