oj.uz

Submission #49213

# Submission time Handle Problem Language Result Execution time Memory
49213 2018-05-23T21:40:19 Z spencercompton Tents (JOI18_tents) C++14
48 / 100
 2000 ms 64632 KB 
#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.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 4 ms 1128 KB Output is correct
3 Correct 3 ms 1128 KB Output is correct
4 Correct 3 ms 1128 KB Output is correct
5 Correct 40 ms 1548 KB Output is correct
6 Correct 18 ms 1548 KB Output is correct
7 Correct 42 ms 1548 KB Output is correct
8 Correct 9 ms 1548 KB Output is correct
9 Correct 2 ms 1548 KB Output is correct
10 Correct 49 ms 1548 KB Output is correct
11 Correct 11 ms 1980 KB Output is correct
12 Correct 230 ms 2028 KB Output is correct

Subtask #2
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 4 ms 1128 KB Output is correct
3 Correct 3 ms 1128 KB Output is correct
4 Correct 3 ms 1128 KB Output is correct
5 Correct 40 ms 1548 KB Output is correct
6 Correct 18 ms 1548 KB Output is correct
7 Correct 42 ms 1548 KB Output is correct
8 Correct 9 ms 1548 KB Output is correct
9 Correct 2 ms 1548 KB Output is correct
10 Correct 49 ms 1548 KB Output is correct
11 Correct 11 ms 1980 KB Output is correct
12 Correct 230 ms 2028 KB Output is correct
13 Correct 84 ms 53488 KB Output is correct
14 Correct 3 ms 53488 KB Output is correct
15 Execution timed out 2071 ms 64632 KB Time limit exceeded
16 Halted 0 ms 0 KB -