Submission #202970

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
202970	2020-02-18T19:48:19 Z	algorithm16	Retro (COCI17_retro)	C++14	35 / 100	169 ms	92412 KB

retro

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,d[3]={1,0,-1},y1;
pair <int,string> dp[105][105][105];
char c[105][105];
pair <int,string> rek(int x,int y,int sum) {
	if(x==-1) {
		//cout << x << " " << y << " " << sum << "\n";
		if(sum==0) return make_pair(0,"");
		else return make_pair(-1e9,"");
	}
	if(dp[x][y][sum].first!=-1) return dp[x][y][sum];
	string ret="";
	int b=-1e9;
	for(int i=0;i<3;i++) {
		if(y+d[i]<0 or y+d[i]>=m) continue;
		int y2=y+d[i],a=0,cnt=0;
		if(c[x][y2]=='(') a=1;
		if(c[x][y2]==')') {
			if(sum==0) continue;
			a=-1;
		}
		string s;
		if(a!=0) s+=c[x][y2];
		if(c[x][y2]=='*') {
			s+=rek(-1,y2,sum+a).second;
			cnt=rek(-1,y2,sum+a).first;
		}
		else {
			s+=rek(x-1,y2,sum+a).second;
			cnt=rek(x-1,y2,sum+a).first+(a!=0);
		}
		//if(x==2 && y==1 && sum==1) cout << a << " " << s << "\n";
		if(cnt<0) continue;
		if(ret.size()==0 && s.size()==0) {
			ret=s;
			b=cnt;
		}
		if(cnt>ret.size() or (cnt==ret.size() && s<ret)) {
			ret=s;
			b=cnt;
		}
	}
	//cout << x << " " << y << " " << sum << " " << b << " " << ret << "\n";
	dp[x][y][sum]=make_pair(b,ret);
	return make_pair(b,ret);
}
int main()
{
	cin >> n >> m;
	for(int i=0;i<n;i++) {
		for(int j=0;j<m;j++) {
			cin >> c[i][j];
			if(c[i][j]=='M') y1=j;
			for(int k=0;k<=n;k++) dp[i][j][k]=make_pair(-1,"a");
		}
	}
	cout << rek(n-1,y1,0).first << "\n" << rek(n-1,y1,0).second;
	return 0;
}

Compilation message

retro.cpp: In function 'std::pair<int, std::__cxx11::basic_string<char> > rek(int, int, int)':
retro.cpp:42:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(cnt>ret.size() or (cnt==ret.size() && s<ret)) {
      ~~~^~~~~~~~~~~
retro.cpp:42:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(cnt>ret.size() or (cnt==ret.size() && s<ret)) {
                         ~~~^~~~~~~~~~~~

Subtask #1

35.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	33 ms	45560 KB	Output is correct
2	Correct	33 ms	45560 KB	Output is correct
3	Correct	34 ms	45560 KB	Output is correct
4	Incorrect	34 ms	45560 KB	Output isn't correct
5	Correct	34 ms	45560 KB	Output is correct
6	Correct	55 ms	46072 KB	Output is correct
7	Correct	57 ms	46072 KB	Output is correct
8	Incorrect	55 ms	46328 KB	Output isn't correct
9	Incorrect	91 ms	47352 KB	Output isn't correct
10	Correct	90 ms	47096 KB	Output is correct
11	Runtime error	161 ms	92280 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
12	Runtime error	162 ms	92408 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
13	Runtime error	122 ms	92408 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
14	Runtime error	118 ms	92280 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
15	Runtime error	168 ms	92408 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
16	Runtime error	169 ms	92280 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
17	Runtime error	150 ms	92412 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
18	Runtime error	152 ms	92408 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
19	Runtime error	164 ms	92280 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
20	Runtime error	166 ms	92408 KB	Execution killed with signal 11 (could be triggered by violating memory limits)