Submission #161524

#	Time	Username	Problem	Language	Result	Execution time	Memory
161524		Ort	Retro (COCI17_retro)	C++11	8 / 100	137 ms	95844 KiB

retro

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/rope>
#define mem(a, b) memset(a, (b), sizeof(a))
#define all(c) (c).begin(),(c).end()
#define sz(a) ((int)(a.size()))
#define ll long long
#define linf (ll)1e18
#define inf (int)1e9
#define minf 0x3F3F3F3F
#define pb push_back
#define fs first
#define sc second
#define mp make_pair
#define mod 1000000007
#define IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define MAX 305
#define watch(x) cerr<<#x<<" = "<<(x)<<endl;

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

template<class T> using indexed_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

int n, m;
int DP[MAX][MAX][MAX];
char MAT[MAX][MAX];
bool isreachable[MAX][MAX];

// testiramo samo za partialy correct

int main() {
	scanf("%d%d", &n, &m);
	for(int i=1;i<=n;i++) scanf("%s", MAT[i]+1);
	
//	clock_t z = clock();
	
	for(int i=1;i<=m;i++) 
		if(MAT[n][i]=='M') {
			isreachable[n][i] = true;
			break;
		}
	
	for(int i=n-1;i>=1;i--)
		for(int j=1;j<=m;j++)
			isreachable[i][j] |= isreachable[i+1][j] |= isreachable[i+1][j-1] |= isreachable[i+1][j+1];
	
	for(int i=n-1;i>=1;i--)
		for(int j=1;j<=m;j++) {
			if(!isreachable[i][j]) continue;
			for(int k=0;k<300;k++) {
				
				if(MAT[i][j]=='*') {
					continue;
				}
				
				if(MAT[i][j]=='.') {
					DP[i][j][k] = max(DP[i+1][j][k], max(DP[i+1][j-1][k], DP[i+1][j+1][k]));
					continue;
				}
				
				if(MAT[i][j]=='(' && k>0) {
					DP[i][j][k] = max(DP[i+1][j][k-1], max(DP[i+1][j-1][k-1], DP[i+1][j+1][k-1])) + 1;
					continue;
				}
				
				if(MAT[i][j]==')') {
					DP[i][j][k] = max(DP[i+1][j][k+1], max(DP[i+1][j-1][k+1], DP[i+1][j+1][k+1]));
					continue;
				}
		
			}
		}
			
	int best = 0;
	
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=m;j++) {
			if(!isreachable[i][j]) continue;
			best = max(best, DP[i][j][0]);
		}
	}
			
	cout << best*2 <<"\n";
	
	cout << "()";
	
//	cout << (double)(clock() - z) / CLOCKS_PER_SEC;
	
	
	
	
	
	return 0;
}

Compilation message (stderr)

retro.cpp: In function 'int main()':
retro.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~
retro.cpp:38:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%s", MAT[i]+1);
                        ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 8 / 100