oj.uz

Submission #72506

# Submission time Handle Problem Language Result Execution time Memory
72506 2018-08-26T08:39:12 Z 이시대의진정한망겜스타투(#2267, cki86201, ainta) Dstorv (FXCUP3_dstorv) C++17
9 / 100
 3 ms 744 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 * (ll)pw(r + h) % MOD)) % MOD;
			res = (res + dfs(x ^ 1<<v[i-1], (ll)pos * r % MOD * (ll)pw(r + h) % 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 main() {
	memset(dp, -1, sizeof dp);
	scanf("%d%d%d", &N, &r, &h);
	scanf("%s", X);
	scanf("%d%d", &A, &B);
	if(N <= 15) {
		printf("%d\n", dfs((1<<N) - 1, 1));
		return 0;
	}
	return 0;
}

Compilation message

dstorv.cpp: In function 'int main()':
dstorv.cpp:77: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:78:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", X);
  ~~~~~^~~~~~~~~
dstorv.cpp:79: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 560 KB Output is correct
4 Correct 2 ms 700 KB Output is correct
5 Correct 2 ms 700 KB Output is correct
6 Correct 3 ms 700 KB Output is correct
7 Correct 2 ms 700 KB Output is correct
8 Correct 3 ms 700 KB Output is correct
9 Correct 3 ms 700 KB Output is correct
10 Correct 3 ms 700 KB Output is correct
11 Correct 3 ms 700 KB Output is correct
12 Correct 3 ms 700 KB Output is correct
13 Correct 2 ms 700 KB Output is correct

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 744 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 560 KB Output is correct
4 Correct 2 ms 700 KB Output is correct
5 Correct 2 ms 700 KB Output is correct
6 Correct 3 ms 700 KB Output is correct
7 Correct 2 ms 700 KB Output is correct
8 Correct 3 ms 700 KB Output is correct
9 Correct 3 ms 700 KB Output is correct
10 Correct 3 ms 700 KB Output is correct
11 Correct 3 ms 700 KB Output is correct
12 Correct 3 ms 700 KB Output is correct
13 Correct 2 ms 700 KB Output is correct
14 Incorrect 3 ms 744 KB Output isn't correct
15 Halted 0 ms 0 KB -