Submission #49213

#	Time	Username	Problem	Language	Result	Execution time	Memory
49213		spencercompton	Tents (JOI18_tents)	C++14	48 / 100	2071 ms	64632 KiB

tents

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
	int r, c;
	cin >> r >> c;
	ll mod = 1000000007LL;
	ll prev[c+1][c+1];
	for(int i = 0; i<=c; i++){
		for(int j = 0; j<=c; j++){
			prev[i][j] = 1LL;
		}
	}
	for(int row = r-1; row>=0; row--){
		ll cur[c+1][c+1];
		for(int x = 0; x<=c; x++){
			for(int y = 0; y<=c; y++){
				if(x+y>c){
					cur[x][y] = 0LL;
					continue;
				}
				//put 2
				ll now = 0LL;
				if(y>=2){
					now += ((ll)(y-1)*(ll)y)/2LL*prev[x][y-2];
					now %= mod;
				}
				//put 1 to pair with above
				if(x>=1){
					now += x*prev[x-1][y];
					now %= mod;
				}
				//put 1 in one of 3 bad directions
				if(y>=1){
					now += 3LL*y*prev[x][y-1];
					now %= mod;
				}
				//put 1 in ok direction
				if(y>=1){
					now += y*prev[x+1][y-1];
					now %= mod;
				}
				now += prev[x][y];
				now %= mod;
				cur[x][y] = now;
			}
		}
		for(int x = 0; x<=c; x++){
			for(int y = 0; y<=c; y++){
				prev[x][y] = cur[x][y];
			}
		}
	}
	prev[0][c] += mod-1;
	prev[0][c] %= mod;
	cout << prev[0][c] << endl;
}

• Subtask 1: 48 / 48
• Subtask 2: 0 / 52