oj.uz

Submission #66514

# Submission time Handle Problem Language Result Execution time Memory
66514 2018-08-11T09:20:03 Z imsifile Dstorv (FXCUP3_dstorv) C++
0 / 100
 2 ms 1176 KB 
#include<stdio.h>

typedef long long lld;
const lld mod = 1000000007;

lld ex(lld a, lld b){
	lld gop=1;
	for(; b; b>>=1){
		if(b&1) gop=gop*a%mod;
		a=a*a%mod;
	}
	return gop;
}

lld r, h, rh, dy1[5050][5050], dy2[5050][5050];
int N, A, B, x, y, xys[5050][2], xyc;
bool chk[5050][5050];
char st[5050];

void make_route(int s){
	int pv=0;
	for(int i=s; i<N; i++){
		if(st[i]=='R'){
			if(pv==-1) xys[xyc][0]=x, xys[xyc][1]=y, xyc++;
			else if(x) chk[x-1][y]=1;
			y++, pv=1;
		}
		else{
			if(pv==1) chk[x][y]=1;
			chk[x][y+1]=1;
			x++, pv=-1;
		}
	}
	chk[x][y+1]=1;
}

int main(){
	scanf("%d%lld%lld", &N, &r, &h), rh=ex(r+h,mod-2);
	r=r*rh%mod, h=h*rh%mod;
	scanf("\n%s", st);
	scanf("%d%d", &A, &B);
	while(N){
		if(st[N-1] != 'R') break;
		N--, A--;
	}
	st[N]=0;
	for(int i=0; i<=N; i++){
		if(i==N || st[i] != 'H'){
			make_route(i);
			N -= i;
			break;
		}
		B--;
	}
	if(A<0 || B<0){ puts("0"); return 0; }
	if(N==0){
		puts(A==0&&B==0 ? "1" : "0");
		return 0;
	}

	dy1[B][0]=1;
	for(int i=0; i<=x; i++){
		for(int j=1; j<=y; j++){
			if(chk[i][j]) continue;
			dy1[i][j] += dy1[i][j-1]*r;
			if(i) dy1[i][j] += dy1[i-1][j]*h;
			dy1[i][j] %= mod;
		}
	}
	dy2[x][y-A]=1;
	for(int i=x-1; i>=0; i--){
		for(int j=y; j>=0; j--){
			if(chk[i][j]) continue;
			dy2[i][j] += dy2[i][j+1]*r;
			dy2[i][j] += dy2[i+1][j]*h;
			dy2[i][j] %= mod;
		}
	}
	if(A==0){ printf("%lld\n", dy1[x][y]); return 0; }
	if(B==0){ printf("%lld\n", dy2[0][0]); return 0; }

	lld sum=0;
	for(int i=0; i<xyc; i++){
		int r=xys[i][0], c=xys[i][1];
		sum += dy1[r][c]*dy2[r][c];
		sum %= mod;
	}
	printf("%lld\n", sum);
	return 0;
}

Compilation message

dstorv.cpp: In function 'int main()':
dstorv.cpp:38:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%lld%lld", &N, &r, &h), rh=ex(r+h,mod-2);
  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
dstorv.cpp:40:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("\n%s", st);
  ~~~~~^~~~~~~~~~~~
dstorv.cpp:41: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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Incorrect 2 ms 536 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1176 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 488 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Incorrect 2 ms 536 KB Output isn't correct
6 Halted 0 ms 0 KB -