oj.uz

Submission #72476

# Submission time Handle Problem Language Result Execution time Memory
72476 2018-08-26T08:26:06 Z (#2175, xdoju, kazel, pps789) Dstorv (FXCUP3_dstorv) C++17
38 / 100
 28 ms 30048 KB 
#include <cstdio>
#include <cstring>
#include <cassert>
using namespace std;

const int MOD = 1000000007;

int N, R, H, A, B;
int RR, RH;

char s[5002];
int upper[5002];

int dp[5002][5002]; // a개의 손을 없앴을 때 b개의 꽃이 죽음

char currentString[30][30];

int inv(int x){
  int v = 1, w = x, z = MOD - 2;

  while(z > 0){
    if(z & 1) v = 1LL * v * w % MOD;
    w = 1LL * w * w % MOD;

    z >>= 1;
  }

  return v;
}

int dfs(int d, int rc, int hc, int ratio){
  // first RH
  int x = 0;

  for(int i = 1; i < N - d; i++){
    if(currentString[d][i] == 'R' && currentString[d][i + 1] == 'H'){
      x = i; break;
    }
  }

  if(x == 0){ // end
    return rc == A && hc == B ? ratio : 0;
  }

  for(int i = 1; i < x; i++) currentString[d + 1][i] = currentString[d][i];
  for(int i = x + 2; i <= N - d; i++) currentString[d + 1][i - 1] = currentString[d][i];

  int res = 0;

  currentString[d + 1][x] = 'R';
  res += dfs(d + 1, rc, hc - 1, 1LL * ratio * RR % MOD);

  currentString[d + 1][x] = 'H';
  res += dfs(d + 1, rc - 1, hc, 1LL * ratio * RH % MOD);

  if(res >= MOD) res -= MOD;

  return res;
}

int main(){
  scanf("%d%d%d", &N, &R, &H);
  scanf("%s", s + 1);
  scanf("%d%d", &A, &B);

  int hc = 0, rc = 0;

  for(int i = 1; i <= N; i++){
    if(s[i] == 'R') rc++;
    else upper[++hc] = rc;
  }

  // printf("rc : %d, hc : %d\n", rc, hc);

  if(A > rc || B > hc){ puts("0"); return 0; }

  int den = inv(R + H);

  RR = 1LL * H * den % MOD; // R이 살아남음
  RH = 1LL * R * den % MOD; // H가 살아남음

  if(N <= 15){ // subtask 1
    for(int i = 1; i <= N; i++) currentString[0][i] = s[i];

    printf("%d\n", dfs(0, rc, hc, 1));
  }
  else{
    if(B != 0) assert(false);

    int res = 1;

    for(int i = 1; i <= rc - A; i++) res = 1LL * res * RH % MOD;
    for(int i = 1; i <= hc; i++) res = 1LL * res * RR % MOD;

    // printf("%d\n", res);

    dp[0][0] = 1;

    for(int i = 1; i <= hc; i++){
      int s = 0;

      // printf("upper : %d\n", upper[i]);

      for(int j = 0; j < upper[i]; j++){
        s += dp[i - 1][j]; if(s >= MOD) s -= MOD;
        dp[i][j] = s;
      }
    }

    int cnt = dp[hc][rc - A];

    printf("%lld\n", 1LL * res * cnt % MOD);
  }
  return 0;
}

Compilation message

dstorv.cpp: In function 'int main()':
dstorv.cpp:62:8: 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:63:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", s + 1);
   ~~~~~^~~~~~~~~~~~~
dstorv.cpp:64:8: 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 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 432 KB Output is correct
4 Correct 2 ms 432 KB Output is correct
5 Correct 2 ms 432 KB Output is correct
6 Correct 2 ms 508 KB Output is correct
7 Correct 3 ms 524 KB Output is correct
8 Correct 3 ms 524 KB Output is correct
9 Correct 3 ms 524 KB Output is correct
10 Correct 3 ms 524 KB Output is correct
11 Correct 2 ms 556 KB Output is correct
12 Correct 2 ms 556 KB Output is correct
13 Correct 3 ms 556 KB Output is correct

Subtask #2
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 732 KB Output is correct
2 Correct 5 ms 3676 KB Output is correct
3 Correct 14 ms 12832 KB Output is correct
4 Correct 21 ms 22728 KB Output is correct
5 Correct 28 ms 30048 KB Output is correct
6 Correct 3 ms 30048 KB Output is correct
7 Correct 2 ms 30048 KB Output is correct
8 Correct 2 ms 30048 KB Output is correct
9 Correct 22 ms 30048 KB Output is correct
10 Correct 20 ms 30048 KB Output is correct
11 Correct 22 ms 30048 KB Output is correct
12 Correct 24 ms 30048 KB Output is correct

Subtask #3
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 432 KB Output is correct
4 Correct 2 ms 432 KB Output is correct
5 Correct 2 ms 432 KB Output is correct
6 Correct 2 ms 508 KB Output is correct
7 Correct 3 ms 524 KB Output is correct
8 Correct 3 ms 524 KB Output is correct
9 Correct 3 ms 524 KB Output is correct
10 Correct 3 ms 524 KB Output is correct
11 Correct 2 ms 556 KB Output is correct
12 Correct 2 ms 556 KB Output is correct
13 Correct 3 ms 556 KB Output is correct
14 Correct 3 ms 732 KB Output is correct
15 Correct 5 ms 3676 KB Output is correct
16 Correct 14 ms 12832 KB Output is correct
17 Correct 21 ms 22728 KB Output is correct
18 Correct 28 ms 30048 KB Output is correct
19 Correct 3 ms 30048 KB Output is correct
20 Correct 2 ms 30048 KB Output is correct
21 Correct 2 ms 30048 KB Output is correct
22 Correct 22 ms 30048 KB Output is correct
23 Correct 20 ms 30048 KB Output is correct
24 Correct 22 ms 30048 KB Output is correct
25 Correct 24 ms 30048 KB Output is correct
26 Runtime error 5 ms 30048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
27 Halted 0 ms 0 KB -