| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 38281 |
2018-01-03T13:25:59 Z |
nibnalin |
Retro (COCI17_retro) |
C++14 |
|
500 ms |
334648 KB |
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int maxn = 305, inf = int(1e5)+5;
const int xx[3] = {-1, -1, -1};
const int yy[3] = {-1, 0, 1};
int r, s, memoi[maxn][maxn][maxn];
pair<int, int> memo[maxn][maxn][maxn];
string A[maxn];
inline bool valid(int x, int y) { return (x >= -1 && y >= 0 && x < r && y < s); }
pair<int, int> DP(int x, int y, int diff)
{
if(x == -1) return {(diff?-inf:0), inf};
else if(diff < 0 || diff > r) return {-inf, inf};
if(A[x][y] == '*') return {(diff?-inf:0), inf};
else if(memo[x][y][diff].first != -1) return memo[x][y][diff];
else if(A[x][y] == '(' || A[x][y] == ')')
{
int c;
pair<int, int> res = {-inf, inf};
if(A[x][y] == '(') c = 1;
else c = -1;
for(int i = 0;i < 3;i++)
{
int u = x+xx[i], v = y+yy[i];
if(valid(u, v))
{
pair<int, int> tmp = DP(u, v, diff+c);
if(tmp.first > res.first) res = tmp, memoi[x][y][diff] = i;
else if(tmp.first == res.first && tmp.second < res.second) res = tmp, memoi[x][y][diff] = i;
}
}
//cout << x << " " << y << " " << diff << " " << c << " " << res.first << " " << res.second << "\n";
return memo[x][y][diff] = {res.first+1, A[x][y]};
}
else
{
pair<int, int> res = {-inf, inf};
for(int i = 0;i < 3;i++)
{
int u = x+xx[i], v = y+yy[i];
if(valid(u, v))
{
pair<int, int> tmp = DP(u, v, diff);
if(tmp.first > res.first) res = tmp, memoi[x][y][diff] = i;
else if(tmp.first == res.first && tmp.second < res.second) res = tmp, memoi[x][y][diff] = i;
}
}
//cout << x << " " << y << " " << diff << " " << res.first << " " << res.second << "\n";
return memo[x][y][diff] = res;
}
}
int main(void)
{
scanf("%d%d", &r, &s);
for(int i = 0;i < r;i++) cin >> A[i];
for(int i = 0;i < maxn;i++)
{
for(int j = 0;j < maxn;j++)
{
for(int k = 0;k < maxn;k++) memo[i][j][k] = {-1, -1}, memoi[i][j][k] = -1;
}
}
int start;
for(int i = 0;i < s;i++)
{
if(A[r-1][i] == 'M') start = i;
}
pair<int, int> res = DP(r-1, start, 0);
pair<int, int> cur = {r-1, start};
int diff = 0;
printf("%d\n", res.first);
/*while(cur.first != -1 && A[cur.first][cur.second] != '*')
{
int c = 0;
if(A[cur.first][cur.second] == '(') c = 1;
else if(A[cur.first][cur.second] == ')') c = -1;
int dir = memoi[cur.first][cur.second][diff];
pair<int, int> nex = {cur.first+xx[dir], cur.second+yy[dir]};
if(c != 0) cout << A[cur.first][cur.second];
cur = nex;
diff += c;
}*/
cout << "\n";
}
Compilation message
retro.cpp: In function 'int main()':
retro.cpp:80:17: warning: variable 'cur' set but not used [-Wunused-but-set-variable]
pair<int, int> cur = {r-1, start};
^
retro.cpp:81:6: warning: unused variable 'diff' [-Wunused-variable]
int diff = 0;
^
retro.cpp:62:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &r, &s);
^
retro.cpp:79:39: warning: 'start' may be used uninitialized in this function [-Wmaybe-uninitialized]
pair<int, int> res = DP(r-1, start, 0);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
73 ms |
334516 KB |
Unexpected end of file - token expected |
| 2 |
Incorrect |
43 ms |
334516 KB |
Unexpected end of file - token expected |
| 3 |
Incorrect |
56 ms |
334516 KB |
Unexpected end of file - token expected |
| 4 |
Incorrect |
79 ms |
334516 KB |
Unexpected end of file - token expected |
| 5 |
Incorrect |
73 ms |
334516 KB |
Unexpected end of file - token expected |
| 6 |
Incorrect |
66 ms |
334516 KB |
Unexpected end of file - token expected |
| 7 |
Incorrect |
66 ms |
334516 KB |
Unexpected end of file - token expected |
| 8 |
Incorrect |
83 ms |
334516 KB |
Unexpected end of file - token expected |
| 9 |
Incorrect |
73 ms |
334516 KB |
Unexpected end of file - token expected |
| 10 |
Incorrect |
79 ms |
334516 KB |
Unexpected end of file - token expected |
| 11 |
Execution timed out |
500 ms |
334648 KB |
Execution timed out |
| 12 |
Execution timed out |
500 ms |
334648 KB |
Execution timed out |
| 13 |
Incorrect |
396 ms |
334648 KB |
Unexpected end of file - token expected |
| 14 |
Incorrect |
269 ms |
334648 KB |
Unexpected end of file - token expected |
| 15 |
Execution timed out |
500 ms |
334648 KB |
Execution timed out |
| 16 |
Execution timed out |
500 ms |
334648 KB |
Execution timed out |
| 17 |
Execution timed out |
500 ms |
334648 KB |
Execution timed out |
| 18 |
Execution timed out |
500 ms |
334648 KB |
Execution timed out |
| 19 |
Execution timed out |
500 ms |
334648 KB |
Execution timed out |
| 20 |
Execution timed out |
500 ms |
334648 KB |
Execution timed out |
