oj.uz

Submission #290655

# Submission time Handle Problem Language Result Execution time Memory
290655 2020-09-04T09:32:58 Z Berted Skyscraper (JOI16_skyscraper) C++14
20 / 100
 2000 ms 19064 KB 
#include <iostream>
#include <algorithm>
#define ll long long
const int MD = 1e9 + 7, C = 10000;
using namespace std;

int n, l, ar[101], dp[2][101][11001][3];

int main()
{
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> l;
	if (n == 1) {cout << "1\n"; return 0;}
	for (int i = 0; i < n; i++) {cin >> ar[i];}
	sort(ar, ar + n);
	dp[0][0][C][0] = 1;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= i; j++)
		{
			for (int k = 0; k <= C + l; k++)
			{
				for (int m = 0; m <= 2; m++)
				{
					
					dp[i & 1][j][k][m] = 0;
					if (k + 2 * ar[i - 1] <= C + l && (j > 1 || i == 1)) 
					{
						dp[i & 1][j][k][m] = (dp[i & 1][j][k][m] + (ll)(j - m) * dp[~i & 1][j - 1][k + 2 * ar[i - 1]][m]) % MD;
					}
					
					if (j < i) 
					{
						dp[i & 1][j][k][m] = (dp[i & 1][j][k][m] + (ll)(2 * j - m) * dp[~i & 1][j][k][m]) % MD; 
					}
					
					if (k - 2 * ar[i - 1] >= 0 && j + 1 < i && (j >= m || i == n)) 
					{
						dp[i & 1][j][k][m] = (dp[i & 1][j][k][m] + (ll)j * dp[~i & 1][j + 1][k - 2 * ar[i - 1]][m]) % MD;
					}
					
					if ((j > 1 || i == 1) && k + ar[i - 1] <= C + l && m) {dp[i & 1][j][k][m] = (dp[i & 1][j][k][m] + (ll)(3 - m) * dp[~i & 1][j - 1][k + ar[i - 1]][m - 1]) % MD;}
					if (k - ar[i - 1] >= 0 && m && (j >= m || i == n) && j < i) {dp[i & 1][j][k][m] = (dp[i & 1][j][k][m] + (ll)(3 - m) * dp[~i & 1][j][k - ar[i - 1]][m - 1]) % MD;}

					if (k - C >= -20 && dp[i & 1][j][k][m]) 
					{
						//if (k + 2 * ar[i - 1] <= C + l && (j > 1 || i == 1)) {cout << "New CC : " << i - 1 << " " << j - 1 << " " << k + 2 * ar[i - 1] - C << " " << m << "\n";}
						//if (j < i) cout << "Con 2CC : " << i - 1 << " " << j << " " << k - C << " " << m << "\n";
						//if (k - 2 * ar[i - 1] >= 0 && j + 1 < i && (j >= m || i == n)) {cout << "Merge CC : " << i - 1 << " " << j + 1 << " " << k - 2 * ar[i - 1] - C << " " << m << "\n";}
						//if (j && k + ar[i - 1] <= C + l && m) {cout << "Corner, newCC : " << i - 1 << " " << j - 1 << " " << k + ar[i - 1] - C << " " << m - 1 << "\n";}
						//if (k - ar[i - 1] >= 0 && m && (j >= m || i == n) && j < i) {cout << "Corner, con2oldCC : " << i - 1 << " " << j << " " << k - ar[i - 1] - C << " " << m - 1 << "\n";}
					}
				}
				
			}
		}
	}
	int res = 0;
	for (int i = 0; i <= l; i++)
	{
		res = (res + dp[n & 1][1][C + i][2]) % MD;
	}
	cout << res << "\n";
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 768 KB Output is correct
3 Correct 3 ms 896 KB Output is correct
4 Correct 11 ms 1664 KB Output is correct
5 Correct 21 ms 2304 KB Output is correct
6 Correct 21 ms 2296 KB Output is correct
7 Correct 21 ms 2176 KB Output is correct
8 Correct 21 ms 2176 KB Output is correct
9 Correct 22 ms 2304 KB Output is correct
10 Correct 22 ms 2176 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 3192 KB Output is correct
2 Correct 70 ms 3704 KB Output is correct
3 Correct 66 ms 3648 KB Output is correct
4 Correct 68 ms 3704 KB Output is correct
5 Correct 67 ms 3704 KB Output is correct
6 Correct 67 ms 3704 KB Output is correct
7 Correct 68 ms 3576 KB Output is correct
8 Correct 65 ms 3576 KB Output is correct
9 Correct 67 ms 3576 KB Output is correct
10 Correct 67 ms 3616 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 768 KB Output is correct
3 Correct 3 ms 896 KB Output is correct
4 Correct 11 ms 1664 KB Output is correct
5 Correct 21 ms 2304 KB Output is correct
6 Correct 21 ms 2296 KB Output is correct
7 Correct 21 ms 2176 KB Output is correct
8 Correct 21 ms 2176 KB Output is correct
9 Correct 22 ms 2304 KB Output is correct
10 Correct 22 ms 2176 KB Output is correct
11 Correct 48 ms 3192 KB Output is correct
12 Correct 70 ms 3704 KB Output is correct
13 Correct 66 ms 3648 KB Output is correct
14 Correct 68 ms 3704 KB Output is correct
15 Correct 67 ms 3704 KB Output is correct
16 Correct 67 ms 3704 KB Output is correct
17 Correct 68 ms 3576 KB Output is correct
18 Correct 65 ms 3576 KB Output is correct
19 Correct 67 ms 3576 KB Output is correct
20 Correct 67 ms 3616 KB Output is correct
21 Correct 568 ms 10104 KB Output is correct
22 Execution timed out 2087 ms 19064 KB Time limit exceeded
23 Halted 0 ms 0 KB -