oj.uz

Submission #72527

# Submission time Handle Problem Language Result Execution time Memory
72527 2018-08-26T08:49:24 Z 이시대의진정한망겜스타투(#2267, cki86201, ainta) Dstorv (FXCUP3_dstorv) C++17
38 / 100
 273 ms 99564 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>

using namespace std;
typedef long long ll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define szz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ldouble;

const int MOD = 1e9 + 7;
int N, r, h, A, B;
char X[5050];

int pw(int x, int y = MOD - 2) {
	int res = 1;
	while(y) {
		if(y & 1) res = (ll) res * x % MOD;
		x = (ll) x * x % MOD;
		y >>= 1;
	}
	return res;
}

int dp[1<<15];

int dfs(int x, int pos) {
	if(dp[x] != -1) return dp[x];
	vector <int> v;
	for(int i=0;i<N;i++) if(1<<i & x) v.pb(i);
	int res = 0;
	int ok = 1;
	for(int i=1;i<szz(v);i++) {
		if(X[v[i]] == 'H' && X[v[i-1]] == 'R') {
			ok = 0;
			res = (res + dfs(x ^ 1<<v[i], (ll)pos * h % MOD)) % MOD;
			res = (res + dfs(x ^ 1<<v[i-1], (ll)pos * r % MOD)) % MOD;
			break;
		}
	}
	if(ok) {
		int ca = 0, cb = 0;
		for(int e : v) {
			if(X[e] == 'R') ca++;
			else cb++;
		}
		if(ca == A && cb == B) return dp[x] = pos;
		else dp[x] = 0;
		return dp[x];
	}
	return dp[x] = res;
}

int D[5050][5050];

int main() {
	memset(dp, -1, sizeof dp);
	scanf("%d%d%d", &N, &r, &h);
	int tr = r * (ll) pw(r + h) % MOD;
	int th = h * (ll) pw(r + h) % MOD;
	r = tr; h = th;
	scanf("%s", X);
	scanf("%d%d", &A, &B);
	if(N <= 15) {
		printf("%d\n", dfs((1<<N) - 1, 1));
	}
	else if(B == 0) {
		D[0][0] = 1;
		for(int i=1;i<=N;i++) {
			char ch = X[i-1];
			if(ch == 'R') {
				for(int j=1;j<=N;j++) D[i][j] = D[i-1][j-1];
			}
			else {
				D[i][N] = (ll)D[i-1][N] * h % MOD;
				for(int j=N-1;j;j--) {
					D[i][j] = ((ll)D[i][j+1] * r + (ll)D[i-1][j] * h) % MOD;
				}
			}
		}
		printf("%d\n", D[N][A]);
	}
	return 0;
}

Compilation message

dstorv.cpp: In function 'int main()':
dstorv.cpp:79:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &N, &r, &h);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
dstorv.cpp:83:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", X);
  ~~~~~^~~~~~~~~
dstorv.cpp:84:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &A, &B);
  ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 3 ms 520 KB Output is correct
4 Correct 3 ms 536 KB Output is correct
5 Correct 2 ms 536 KB Output is correct
6 Correct 3 ms 724 KB Output is correct
7 Correct 3 ms 724 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 3 ms 724 KB Output is correct
10 Correct 2 ms 724 KB Output is correct
11 Correct 3 ms 724 KB Output is correct
12 Correct 3 ms 724 KB Output is correct
13 Correct 3 ms 724 KB Output is correct

Subtask #2
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1084 KB Output is correct
2 Correct 18 ms 11068 KB Output is correct
3 Correct 82 ms 57464 KB Output is correct
4 Correct 171 ms 99516 KB Output is correct
5 Correct 139 ms 99516 KB Output is correct
6 Correct 217 ms 99516 KB Output is correct
7 Correct 100 ms 99516 KB Output is correct
8 Correct 273 ms 99516 KB Output is correct
9 Correct 183 ms 99516 KB Output is correct
10 Correct 189 ms 99516 KB Output is correct
11 Correct 177 ms 99564 KB Output is correct
12 Correct 182 ms 99564 KB Output is correct

Subtask #3
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 3 ms 520 KB Output is correct
4 Correct 3 ms 536 KB Output is correct
5 Correct 2 ms 536 KB Output is correct
6 Correct 3 ms 724 KB Output is correct
7 Correct 3 ms 724 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 3 ms 724 KB Output is correct
10 Correct 2 ms 724 KB Output is correct
11 Correct 3 ms 724 KB Output is correct
12 Correct 3 ms 724 KB Output is correct
13 Correct 3 ms 724 KB Output is correct
14 Correct 3 ms 1084 KB Output is correct
15 Correct 18 ms 11068 KB Output is correct
16 Correct 82 ms 57464 KB Output is correct
17 Correct 171 ms 99516 KB Output is correct
18 Correct 139 ms 99516 KB Output is correct
19 Correct 217 ms 99516 KB Output is correct
20 Correct 100 ms 99516 KB Output is correct
21 Correct 273 ms 99516 KB Output is correct
22 Correct 183 ms 99516 KB Output is correct
23 Correct 189 ms 99516 KB Output is correct
24 Correct 177 ms 99564 KB Output is correct
25 Correct 182 ms 99564 KB Output is correct
26 Incorrect 2 ms 99564 KB Output isn't correct
27 Halted 0 ms 0 KB -