Submission #38324

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
38324	2018-01-03T17:02:02 Z	b00n0rp	Retro (COCI17_retro)	C++14	4 / 100	133 ms	224564 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	23 ms	224564 KB	Output isn't correct
2	Partially correct	9 ms	224564 KB	Partially correct
3	Runtime error	49 ms	224564 KB	Execution killed because of forbidden syscall writev (20)
4	Incorrect	23 ms	224564 KB	Integer 0 violates the range [1, 100000]
5	Incorrect	19 ms	224564 KB	Output isn't correct
6	Runtime error	19 ms	224564 KB	Execution killed because of forbidden syscall writev (20)
7	Incorrect	33 ms	224564 KB	Output isn't correct
8	Partially correct	36 ms	224564 KB	Partially correct
9	Runtime error	29 ms	224564 KB	Execution killed because of forbidden syscall writev (20)
10	Runtime error	33 ms	224564 KB	Execution killed because of forbidden syscall writev (20)
11	Runtime error	99 ms	224564 KB	Execution killed because of forbidden syscall writev (20)
12	Runtime error	93 ms	224564 KB	Execution killed because of forbidden syscall writev (20)
13	Runtime error	59 ms	224564 KB	Execution killed because of forbidden syscall writev (20)
14	Runtime error	49 ms	224564 KB	Execution killed because of forbidden syscall writev (20)
15	Runtime error	106 ms	224564 KB	Execution killed because of forbidden syscall writev (20)
16	Runtime error	106 ms	224564 KB	Execution killed because of forbidden syscall writev (20)
17	Runtime error	133 ms	224564 KB	Execution killed because of forbidden syscall writev (20)
18	Runtime error	93 ms	224564 KB	Execution killed because of forbidden syscall writev (20)
19	Runtime error	129 ms	224564 KB	Execution killed because of forbidden syscall writev (20)
20	Incorrect	116 ms	224564 KB	Output isn't correct