Submission #220148

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
220148	2020-04-07T07:02:04 Z	kshitij_sodani	Tents (JOI18_tents)	C++17	100 / 100	211 ms	70776 KB

tents

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cstdio>

using namespace std;
#define pb push_back
#define a first
#define b second
typedef long long int llo;
llo mod=1000000007;
int main(){
	llo n,m;
	cin>>n>>m;
	llo dp[n][m];
	dp[0][0]=5;
	for(llo i=1;i<n;i++){
		dp[i][0]=4*(i+1)+((i+1)*i)/2;
		dp[i][0]+=1;
		dp[i][0]%=mod;
	}
	for(llo j=1;j<m;j++){
		dp[0][j]=4*(j+1)+((j+1)*j)/2;
		dp[0][j]+=1;
		dp[0][j]%=mod;
	}
	for(llo i=1;i<n;i++){
		for(llo j=1;j<m;j++){
			dp[i][j]=4*(j+1)*dp[i-1][j-1];
			dp[i][j]+=dp[i-1][j];
			if(i>1){
				dp[i][j]+=dp[i-2][j-1]*(((j+1)*(i))%mod);
			}
			else{
				dp[i][j]+=(((j+1)*i)%mod);
			}
			if(j>1){
				dp[i][j]+=((((j+1)*j)/2)%mod)*dp[i-1][j-2];
			}
			else{
				dp[i][j]+=((j+1)*j)/2;
			}
			dp[i][j]%=mod;
		}
	}
	/*for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cout<<dp[i][j]<<" ";
		}
		cout<<endl;
	}*/
	cout<<(dp[n-1][m-1]+mod-1)%mod<<endl;

	return 0;
}

Subtask #1

48.0 / 48.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	256 KB	Output is correct
2	Correct	4 ms	256 KB	Output is correct
3	Correct	4 ms	256 KB	Output is correct
4	Correct	4 ms	256 KB	Output is correct
5	Correct	5 ms	384 KB	Output is correct
6	Correct	5 ms	512 KB	Output is correct
7	Correct	5 ms	512 KB	Output is correct
8	Correct	5 ms	384 KB	Output is correct
9	Correct	4 ms	256 KB	Output is correct
10	Correct	5 ms	640 KB	Output is correct
11	Correct	4 ms	384 KB	Output is correct
12	Correct	7 ms	1024 KB	Output is correct

Subtask #2

52.0 / 52.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	256 KB	Output is correct
2	Correct	4 ms	256 KB	Output is correct
3	Correct	4 ms	256 KB	Output is correct
4	Correct	4 ms	256 KB	Output is correct
5	Correct	5 ms	384 KB	Output is correct
6	Correct	5 ms	512 KB	Output is correct
7	Correct	5 ms	512 KB	Output is correct
8	Correct	5 ms	384 KB	Output is correct
9	Correct	4 ms	256 KB	Output is correct
10	Correct	5 ms	640 KB	Output is correct
11	Correct	4 ms	384 KB	Output is correct
12	Correct	7 ms	1024 KB	Output is correct
13	Correct	4 ms	384 KB	Output is correct
14	Correct	5 ms	384 KB	Output is correct
15	Correct	134 ms	44024 KB	Output is correct
16	Correct	13 ms	3072 KB	Output is correct
17	Correct	33 ms	10104 KB	Output is correct
18	Correct	41 ms	12408 KB	Output is correct
19	Correct	154 ms	51320 KB	Output is correct
20	Correct	124 ms	41080 KB	Output is correct
21	Correct	96 ms	27128 KB	Output is correct
22	Correct	84 ms	26744 KB	Output is correct
23	Correct	49 ms	15224 KB	Output is correct
24	Correct	211 ms	70776 KB	Output is correct
25	Correct	161 ms	52524 KB	Output is correct
26	Correct	184 ms	60156 KB	Output is correct
27	Correct	205 ms	67960 KB	Output is correct