Submission #38326

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
38326	2018-01-03T17:02:53 Z	b00n0rp	Retro (COCI17_retro)	C++14	4 / 100	500 ms	224404 KB

retro

/*input
6 3
((.
*..
(**
)()
().
M..
*/		
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define int ll
#define pb push_back
#define INF 1000000000
#define MOD 1000000007
#define mp make_pair
const double PI=3.141592653589793238462643383279502884197169399375105820974944;
#define REP(i,n) for (int i = 0; i < n; i++)
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define REPD(i,n) for (int i = n-1; i >= 0; i--)
#define FORD(i,a,b) for (int i = a; i >= b; i--)
#define remax(a,b) a = max(a,b)
#define remin(a,b) a = min(a,b)
#define all(v) v.begin(),v.end()
#define pii pair<int,int>
#define F first
#define S second
#define mii map<int,int>
#define vi vector<int>
#define vvi vector<vi>
#define itr :: iterator it
#define WL(t) while(t --)
#define gcd(a,b) __gcd((a),(b))
#define lcm(a,b) ((a)*(b))/gcd((a),(b))
#define print(arr) for (auto it = arr.begin(); it != arr.end(); ++it) cout << *it << " "; cout << endl;
#define debug(x) cout << x << endl;
#define debug2(x,y) cout << x << " " << y << endl;
#define debug3(x,y,z) cout << x << " " << y << " " << z << endl;

int power(int a,int b,int m = MOD){
	if(b == 0) return 1;
	if(b == 1) return a;
	int x = power(a,b/2,m)%m;
	x = (x*x)%m;
	if(b%2) return (x*a)%m;
	return x;
}

int n,m;
int a[305][305],dp[305][305][305];
pii s;

void solve(){
	cin >> n >> m;
	REP(i,n){
		REP(j,m){
			char c; cin >> c;
			if(c == '.') a[i][j] = 0;
			else if(c == '(') a[i][j] = 1;
			else if(c == ')') a[i][j] = -1;
			else if(c == 'M') a[i][j] = 0,s = {i,j};
			else a[i][j] = 10;
		}
	}
	REP(i,305) REP(j,305) REP(k,305) dp[i][j][k] = -INF;
	REP(j,m){
		if(a[0][j]%10 == 0) dp[0][j][0] = 0;
		if(a[0][j] == -1) dp[0][j][1] = 1;
	}
	FOR(i,1,n){
		REP(j,m){
			if(a[i][j] == 10){
				dp[i][j][0] = 0;
				continue;
			}
			REP(k,n){
				if(a[i][j] == 0){
					dp[i][j][k] = max(dp[i-1][max((ll)0,j-1)][k],dp[i-1][j-1][k-1]);
					remax(dp[i][j][k],dp[i-1][j+1][k]);
				}
				else{
					if(k == 0){
						if(a[i][j] == -1) continue;
					}
					dp[i][j][k] = dp[i-1][j][k+a[i][j]];
					if(j) remax(dp[i][j][k],dp[i-1][j-1][k+a[i][j]]);
					remax(dp[i][j][k],dp[i-1][j+1][k+a[i][j]]);
					dp[i][j][k] ++;
				}
				// cout << i << " " << j << " " << k << " " << dp[i][j][k] << endl;
			}
		}
	}
	cout << dp[s.F][s.S][0] << endl;
	REP(i,dp[s.F][s.S][0]) cout << "("; cout << "\n";
}

signed main(){
	// ios_base::sync_with_stdio(false);
	// cin.tie(0);
	// cout.tie(0);

	int t = 1;
	// cin >> t;
	WL(t) solve();
}

Subtask #1

4.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	9 ms	224404 KB	Output isn't correct
2	Partially correct	36 ms	224404 KB	Partially correct
3	Execution timed out	500 ms	224404 KB	Execution timed out
4	Incorrect	39 ms	224404 KB	Integer 0 violates the range [1, 100000]
5	Incorrect	26 ms	224404 KB	Output isn't correct
6	Execution timed out	500 ms	224404 KB	Execution timed out
7	Incorrect	49 ms	224404 KB	Output isn't correct
8	Partially correct	16 ms	224404 KB	Partially correct
9	Execution timed out	500 ms	224404 KB	Execution timed out
10	Execution timed out	500 ms	224404 KB	Execution timed out
11	Execution timed out	500 ms	224404 KB	Execution timed out
12	Execution timed out	500 ms	224404 KB	Execution timed out
13	Execution timed out	500 ms	224404 KB	Execution timed out
14	Execution timed out	500 ms	224404 KB	Execution timed out
15	Execution timed out	500 ms	224404 KB	Execution timed out
16	Execution timed out	500 ms	224404 KB	Execution timed out
17	Execution timed out	500 ms	224404 KB	Execution timed out
18	Execution timed out	500 ms	224404 KB	Execution timed out
19	Execution timed out	500 ms	0 KB	Execution timed out
20	Incorrect	106 ms	224404 KB	Output isn't correct