| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 40087 |
2018-01-26T15:33:01 Z |
Hebisuke |
Retro (COCI17_retro) |
C++14 |
|
371 ms |
335268 KB |
#include "stdio.h"
#include "queue"
#include "algorithm"
#include "stack"
using namespace std;
queue<pair<int,pair<int, int> > > q;
int dp[305][305][305],s,r,x,y;
char tb[305][305];
pair<int, int > p[305][305][305];
stack<char> st;
main()
{
scanf("%d %d",&r,&s);
for(int i=0;i<r;i++)
scanf("%s",tb[i]);
for(int i=0;i<r;i++)
for(int j=0;j<s;j++){
for(int k=0;k<r;k++) {dp[i][j][k]=-1;p[i][j][k]=make_pair(j,k);}
}
for(int i=0;i<s;i++) if(tb[r-1][i]=='M') {q.push(make_pair(r-1,make_pair(i,0)));dp[r-1][i][0]=0;
break;}
while(!q.empty())
{
int rr=q.front().first, cc=q.front().second.first , f=q.front().second.second;
q.pop();
//printf("%d %d %d\n",rr,cc,f);
if(rr==0) continue;
if(cc>0)
{
char temp = tb[rr-1][cc-1];
if(temp=='(') {
if(dp[rr-1][cc-1][f+1]<=dp[rr][cc][f])
{
dp[rr-1][cc-1][f+1]=dp[rr][cc][f];
p[rr-1][cc-1][f+1]=make_pair(cc,f);
}
q.push(make_pair(rr-1,make_pair(cc-1,f+1)));
}
else if(temp==')') {
if(f>=1){
if(dp[rr-1][cc-1][f-1]<dp[rr][cc][f]+2)
{
dp[rr-1][cc-1][f-1]=dp[rr][cc][f]+2;
p[rr-1][cc-1][f-1]=make_pair(cc,f);
}else if(dp[rr-1][cc-1][f-1]==dp[rr][cc][f]+2&&tb[rr][cc]==')')
{
p[rr-1][cc-1][f-1]=make_pair(cc,f);
}
q.push(make_pair(rr-1,make_pair(cc-1,f-1)));}
}
else {
if(dp[rr-1][cc-1][f]<dp[rr][cc][f])
{
dp[rr-1][cc-1][f]=dp[rr][cc][f];
p[rr-1][cc-1][f]=make_pair(cc,f);
if(temp!='*') q.push(make_pair(rr-1,make_pair(cc-1,f)));
}
}
}
if(cc<s-1)
{
char temp = tb[rr-1][cc+1];
if(temp=='(') {
if(dp[rr-1][cc+1][f+1]<=dp[rr][cc][f])
{
dp[rr-1][cc+1][f+1]=dp[rr][cc][f];
p[rr-1][cc+1][f+1]=make_pair(cc,f);
}
q.push(make_pair(rr-1,make_pair(cc+1,f+1)));
}
else if(temp==')') {
if(f>=1){
if(dp[rr-1][cc+1][f-1]<dp[rr][cc][f]+2)
{
dp[rr-1][cc+1][f-1]=dp[rr][cc][f]+2;
p[rr-1][cc+1][f-1]=make_pair(cc,f);
}
else if(dp[rr-1][cc+1][f-1]==dp[rr][cc][f]+2&&tb[rr][cc]==')')
{
p[rr-1][cc+1][f-1]=make_pair(cc,f);
}
q.push(make_pair(rr-1,make_pair(cc+1,f-1)));}
}
else {
if(dp[rr-1][cc+1][f]<dp[rr][cc][f])
{
dp[rr-1][cc+1][f]=dp[rr][cc][f];
p[rr-1][cc+1][f]=make_pair(cc,f);
if(temp!='*') q.push(make_pair(rr-1,make_pair(cc+1,f)));
}
}
}
char temp = tb[rr-1][cc];
if(temp=='(') {
if(dp[rr-1][cc][f+1]<=dp[rr][cc][f])
{
dp[rr-1][cc][f+1]=dp[rr][cc][f];
p[rr-1][cc][f+1]=make_pair(cc,f);
}
q.push(make_pair(rr-1,make_pair(cc,f+1)));
}
else if(temp==')') {
if(f>=1){
if(dp[rr-1][cc][f-1]<dp[rr][cc][f]+2)
{
dp[rr-1][cc][f-1]=dp[rr][cc][f]+2;
p[rr-1][cc][f-1]=make_pair(cc,f);
}
else if(dp[rr-1][cc][f-1]==dp[rr][cc][f]+2&&tb[rr][cc]==')')
{
p[rr-1][cc][f-1]=make_pair(cc,f);
}
q.push(make_pair(rr-1,make_pair(cc,f-1)));}
}
else {
if(dp[rr-1][cc][f]<dp[rr][cc][f])
{
dp[rr-1][cc][f]=dp[rr][cc][f];
p[rr-1][cc][f]=make_pair(cc,f);
if(temp!='*') q.push(make_pair(rr-1,make_pair(cc,f)));
}
}
}
int ma=0;
for(int i=0;i<r;i++)
for(int j=0;j<s;j++) if(dp[i][j][0]>ma) {ma=dp[i][j][0];x=i;y=j;}
int k=0;
while(x!=r-1)
{
if(tb[x][y]=='('||tb[x][y]==')')
{
st.push(tb[x][y]);
}
int a = p[x][y][k].first, b= p[x][y][k].second;
y=a;
k=b;
x++;
}
printf("%d\n",ma);
while(!st.empty())
{
printf("%c",st.top());
st.pop();
}
}
Compilation message
retro.cpp:12:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main()
^
retro.cpp: In function 'int main()':
retro.cpp:14:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&r,&s);
^
retro.cpp:16:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s",tb[i]);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
0 ms |
334516 KB |
Partially correct |
| 2 |
Correct |
1 ms |
334516 KB |
Output is correct |
| 3 |
Partially correct |
0 ms |
334516 KB |
Partially correct |
| 4 |
Correct |
1 ms |
334516 KB |
Output is correct |
| 5 |
Correct |
0 ms |
334516 KB |
Output is correct |
| 6 |
Partially correct |
10 ms |
334648 KB |
Partially correct |
| 7 |
Partially correct |
6 ms |
334516 KB |
Partially correct |
| 8 |
Partially correct |
11 ms |
334516 KB |
Partially correct |
| 9 |
Partially correct |
14 ms |
334516 KB |
Partially correct |
| 10 |
Partially correct |
18 ms |
334648 KB |
Partially correct |
| 11 |
Partially correct |
276 ms |
335032 KB |
Partially correct |
| 12 |
Partially correct |
262 ms |
335036 KB |
Partially correct |
| 13 |
Partially correct |
149 ms |
334780 KB |
Partially correct |
| 14 |
Partially correct |
132 ms |
334648 KB |
Partially correct |
| 15 |
Partially correct |
371 ms |
335268 KB |
Partially correct |
| 16 |
Partially correct |
325 ms |
335128 KB |
Partially correct |
| 17 |
Partially correct |
297 ms |
335144 KB |
Partially correct |
| 18 |
Partially correct |
238 ms |
334908 KB |
Partially correct |
| 19 |
Partially correct |
359 ms |
335232 KB |
Partially correct |
| 20 |
Partially correct |
301 ms |
335096 KB |
Partially correct |
