Submission #202970

#	Time	Username	Problem	Language	Result	Execution time	Memory
202970		algorithm16	Retro (COCI17_retro)	C++14	35 / 100	169 ms	92412 KiB

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 (stderr)

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 / 100