Submission #38327

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
38327	2018-01-03T17:07:43 Z	b00n0rp	Retro (COCI17_retro)	C++14	40 / 100	119 ms	224404 KB

retro

/*input
8 8
...).).*
*....)..
.)*(..).
(*)((...
.)).)(..
.)(.)..(
...).(.*
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(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]]);
				if(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

40.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	29 ms	224404 KB	Partially correct
2	Partially correct	6 ms	224404 KB	Partially correct
3	Partially correct	19 ms	224404 KB	Partially correct
4	Partially correct	43 ms	224404 KB	Partially correct
5	Partially correct	33 ms	224404 KB	Partially correct
6	Partially correct	29 ms	224404 KB	Partially correct
7	Partially correct	33 ms	224404 KB	Partially correct
8	Partially correct	16 ms	224404 KB	Partially correct
9	Partially correct	26 ms	224404 KB	Partially correct
10	Partially correct	29 ms	224404 KB	Partially correct
11	Partially correct	99 ms	224404 KB	Partially correct
12	Partially correct	83 ms	224404 KB	Partially correct
13	Partially correct	63 ms	224404 KB	Partially correct
14	Partially correct	63 ms	224404 KB	Partially correct
15	Partially correct	109 ms	224404 KB	Partially correct
16	Partially correct	96 ms	224404 KB	Partially correct
17	Partially correct	83 ms	224404 KB	Partially correct
18	Partially correct	93 ms	224404 KB	Partially correct
19	Partially correct	119 ms	224404 KB	Partially correct
20	Partially correct	89 ms	224404 KB	Partially correct