Submission #66558

#	Time	Username	Problem	Language	Result	Execution time	Memory
66558		imsifile	Dstorv (FXCUP3_dstorv)	C++98	100 / 100	296 ms	129300 KiB

dstorv

#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;
int 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 chk[x][y]|=2;
			y++, pv=1;
		}
		else{
			if(pv==1) chk[x][y]|=3;
			chk[x][y]|=1;
			x++, pv=-1;
		}
	}
	chk[0][0]=0;
}

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]&2) 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]&1) 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 (stderr)

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: 9 / 9
• Subtask 2: 29 / 29
• Subtask 3: 62 / 62