oj.uz

Submission #72522

# Submission time Handle Problem Language Result Execution time Memory
72522 2018-08-26T08:47:10 Z 이시대의진정한망겜스타투(#2267, cki86201, ainta) Dstorv (FXCUP3_dstorv) C++17
9 / 100
 3 ms 1084 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>=0;j--) {
					D[i][j] = ((ll)D[i-1][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 520 KB Output is correct
5 Correct 3 ms 568 KB Output is correct
6 Correct 2 ms 644 KB Output is correct
7 Correct 3 ms 644 KB Output is correct
8 Correct 3 ms 644 KB Output is correct
9 Correct 2 ms 644 KB Output is correct
10 Correct 3 ms 644 KB Output is correct
11 Correct 2 ms 644 KB Output is correct
12 Correct 3 ms 644 KB Output is correct
13 Correct 3 ms 644 KB Output is correct

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1084 KB Output isn't correct
2 Halted 0 ms 0 KB -

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 520 KB Output is correct
5 Correct 3 ms 568 KB Output is correct
6 Correct 2 ms 644 KB Output is correct
7 Correct 3 ms 644 KB Output is correct
8 Correct 3 ms 644 KB Output is correct
9 Correct 2 ms 644 KB Output is correct
10 Correct 3 ms 644 KB Output is correct
11 Correct 2 ms 644 KB Output is correct
12 Correct 3 ms 644 KB Output is correct
13 Correct 3 ms 644 KB Output is correct
14 Incorrect 2 ms 1084 KB Output isn't correct
15 Halted 0 ms 0 KB -