oj.uz

Submission #161523

# Submission time Handle Problem Language Result Execution time Memory
161523 2019-11-02T20:39:13 Z Ort Retro (COCI17_retro) C++11
0 / 100
 132 ms 95864 KB 
#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 << "EH";
	
//	cout << (double)(clock() - z) / CLOCKS_PER_SEC;
	
	
	
	
	
	return 0;
}

Compilation message

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
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 632 KB Token "EH" doesn't correspond to pattern "[\(\)]{1,100000}"
2 Incorrect 2 ms 504 KB Token "EH" doesn't correspond to pattern "[\(\)]{1,100000}"
3 Incorrect 2 ms 504 KB Token "EH" doesn't correspond to pattern "[\(\)]{1,100000}"
4 Incorrect 3 ms 760 KB Token "EH" doesn't correspond to pattern "[\(\)]{1,100000}"
5 Incorrect 3 ms 1148 KB Token "EH" doesn't correspond to pattern "[\(\)]{1,100000}"
6 Incorrect 9 ms 5624 KB Token "EH" doesn't correspond to pattern "[\(\)]{1,100000}"
7 Incorrect 9 ms 5368 KB Token "EH" doesn't correspond to pattern "[\(\)]{1,100000}"
8 Incorrect 7 ms 4600 KB Token "EH" doesn't correspond to pattern "[\(\)]{1,100000}"
9 Incorrect 13 ms 8696 KB Token "EH" doesn't correspond to pattern "[\(\)]{1,100000}"
10 Incorrect 17 ms 11384 KB Token "EH" doesn't correspond to pattern "[\(\)]{1,100000}"
11 Incorrect 122 ms 88424 KB Token "EH" doesn't correspond to pattern "[\(\)]{1,100000}"
12 Incorrect 119 ms 88268 KB Token "EH" doesn't correspond to pattern "[\(\)]{1,100000}"
13 Incorrect 62 ms 44152 KB Token "EH" doesn't correspond to pattern "[\(\)]{1,100000}"
14 Incorrect 59 ms 43896 KB Token "EH" doesn't correspond to pattern "[\(\)]{1,100000}"
15 Incorrect 121 ms 84728 KB Token "EH" doesn't correspond to pattern "[\(\)]{1,100000}"
16 Incorrect 120 ms 84472 KB Token "EH" doesn't correspond to pattern "[\(\)]{1,100000}"
17 Incorrect 116 ms 83668 KB Token "EH" doesn't correspond to pattern "[\(\)]{1,100000}"
18 Incorrect 111 ms 83576 KB Token "EH" doesn't correspond to pattern "[\(\)]{1,100000}"
19 Incorrect 132 ms 95864 KB Token "EH" doesn't correspond to pattern "[\(\)]{1,100000}"
20 Incorrect 129 ms 95784 KB Token "EH" doesn't correspond to pattern "[\(\)]{1,100000}"