oj.uz

Submission #586594

# Submission time Handle Problem Language Result Execution time Memory
586594 2022-06-30T12:11:48 Z blue Skyscraper (JOI16_skyscraper) C++17
5 / 100
 2 ms 1108 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

using ll = long long;
using vll = vector<ll>;
using vi = vector<int>;

const ll mod = 1'000'000'0007LL;

ll ad(ll a, ll b)
{
	return (a+b) % mod;
}

ll mul(ll a, ll b)
{
	return (a*b) % mod;
}

void selfadd(int& a, int b)
{
	a = ad(a, b);
}

int N, L;

int validlen(int x)
{
	return 0 <= x && x <= L;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N >> L;

	vi A(1+N, 0);
	for(int i = 1; i <= N; i++)
		cin >> A[i];

	sort(A.begin(), A.end());

	int DP[1+N][1+N][1+L][1+2];

	for(int i = 0; i <= N; i++)
		for(int j = 0; j <= N; j++)
			for(int l = 0; l <= L; l++)
				for(int e = 0; e <= 2; e++)
					DP[i][j][l][e] = 0;

	DP[1][1][0][0] = DP[1][1][0][2] = 1;
	DP[1][1][0][1] = 2;

	for(int i = 1; i <= N; i++)
	{
		// cerr << "\n\n\n";
		for(int j = 1; j <= i; j++)
		{
			// cerr << "\n\n";
			for(int l = 0; l <= L; l++)
			{
				// cerr << "\n";
				for(int e = 0; e <= 2; e++)
				{
					// cerr << i << ' ' << j << ' ' << l << ' ' << e << " : " << DP[i][j][l][e] << '\n';

					if(i >= N)
						continue;

					if(!validlen(l + (2*j - e) * (A[i+1] - A[i])))
						continue;

					// cerr << "proceeding\n";


					//case 1: building i+1 forms new component
		selfadd(DP[i+1][j+1][l + (2*j - e) * (A[i+1] - A[i])][e], mul(DP[i][j][l][e], j+1 - e));

		           //case 2: building i+1 is attached to the left/right of some component
		// if(i == 1 && j == 1 && l == 0 && e == 0)
			// cerr << DP[i][j][l][e] << ' ' << 2*j - e << " -> " << i+1 << ' ' << j << ' ' << l + (2*j - e) * (A[i+1] - A[i]) << ' ' << e << '\n';
		selfadd(DP[i+1][j][l + (2*j - e) * (A[i+1] - A[i])][e], mul(DP[i][j][l][e], 2*j - e));

				   //case 3: building i+1 merges two components
					if(j >= 2)
		selfadd(DP[i+1][j-1][l + (2*j - e) * (A[i+1] - A[i])][e], mul(DP[i][j][l][e], j-1));

				   //case 4: building i+1 creates an endpoint
					if(e < 2)
		selfadd(DP[i+1][j][l + (2*j - e) * (A[i+1] - A[i])][e+1], mul(DP[i][j][l][e], 2 - e));

					//case 5: building i+1 simultaneously forms a new component and creates endpoint
	                if(e < 2)
	    selfadd(DP[i+1][j+1][l + (2*j - e) * (A[i+1] - A[i])][e+1], mul(DP[i][j][l][e], 2 - e));
					}
			}
		}
	}

	int res = 0;

	for(int l = 0; l <= L; l++)
		res = ad(res, DP[N][1][l][2]);

	cout << res << '\n';
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 1108 KB Output is correct
6 Correct 1 ms 1108 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 1088 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Incorrect 2 ms 468 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 1108 KB Output is correct
6 Correct 1 ms 1108 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 1088 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 324 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Incorrect 2 ms 468 KB Output isn't correct
20 Halted 0 ms 0 KB -