oj.uz

Submission #1008562

# Submission time Handle Problem Language Result Execution time Memory
1008562 2024-06-26T14:25:38 Z yellowtoad Skyscraper (JOI16_skyscraper) C++17
20 / 100
 92 ms 164328 KB 
#include <iostream>
#include <algorithm>
using namespace std;

const long long mod = 1e9+7;
long long n, m, a[110], dp[110][1010][110][3], sum;

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> a[i];
	if (n == 1) {
		cout << 1 << endl;
		return 0;
	}
	sort(a+1,a+n+1);
	dp[1][0][1][0] = 1;
	dp[1][0][1][1] = 2;
	for (int i = 2; i <= n; i++) {
		for (int j = 0; j <= m; j++) {
			for (int k = 1; k <= n; k++) {
				if (j >= 2*(k-1)*(a[i]-a[i-1])) (dp[i][j][k][0] += dp[i-1][j-2*(k-1)*(a[i]-a[i-1])][k-1][0]*k)%mod;
				if (j >= 2*(k)*(a[i]-a[i-1])) (dp[i][j][k][0] += dp[i-1][j-2*(k)*(a[i]-a[i-1])][k][0]*2*k)%mod;
				if (j >= 2*(k+1)*(a[i]-a[i-1])) (dp[i][j][k][0] += dp[i-1][j-2*(k+1)*(a[i]-a[i-1])][k+1][0]*k)%mod;
				
				if (j >= 2*(k-1)*(a[i]-a[i-1])) (dp[i][j][k][1] += dp[i-1][j-2*(k-1)*(a[i]-a[i-1])][k-1][0]*2)%mod;
				if (j >= 2*(k)*(a[i]-a[i-1])) (dp[i][j][k][1] += dp[i-1][j-2*(k)*(a[i]-a[i-1])][k][0]*2)%mod;
				
				if (j >= (2*(k-1)-1)*(a[i]-a[i-1])) (dp[i][j][k][1] += dp[i-1][j-(2*(k-1)-1)*(a[i]-a[i-1])][k-1][1]*(k-1))%mod;
				if (j >= (2*(k)-1)*(a[i]-a[i-1])) (dp[i][j][k][1] += dp[i-1][j-(2*(k)-1)*(a[i]-a[i-1])][k][1]*(2*(k)-1))%mod;
				if (j >= (2*(k+1)-1)*(a[i]-a[i-1])) (dp[i][j][k][1] += dp[i-1][j-(2*(k+1)-1)*(a[i]-a[i-1])][k+1][1]*(k))%mod;
				
				if (j >= (2*(k-1)-1)*(a[i]-a[i-1])) (dp[i][j][k][2] += dp[i-1][j-(2*(k-1)-1)*(a[i]-a[i-1])][k-1][1])%mod;
				if (j >= (2*(k)-1)*(a[i]-a[i-1])) (dp[i][j][k][2] += dp[i-1][j-(2*(k)-1)*(a[i]-a[i-1])][k][1])%mod;
				
				if (j >= (2*(k-1)-2)*(a[i]-a[i-1])) (dp[i][j][k][2] += dp[i-1][j-(2*(k-1)-2)*(a[i]-a[i-1])][k-1][2]*(k-2))%mod;
				if (j >= (2*(k)-2)*(a[i]-a[i-1])) (dp[i][j][k][2] += dp[i-1][j-(2*(k)-2)*(a[i]-a[i-1])][k][2]*(2*(k)-2))%mod;
				if (j >= (2*(k+1)-2)*(a[i]-a[i-1])) (dp[i][j][k][2] += dp[i-1][j-(2*(k+1)-2)*(a[i]-a[i-1])][k+1][2]*(k))%mod;
			}
		}
	}
	for (int i = 0; i <= m; i++) (sum += dp[n][i][1][2]) %= mod;
	cout << sum << endl;
}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:21:99: warning: value computed is not used [-Wunused-value]
   21 |     if (j >= 2*(k-1)*(a[i]-a[i-1])) (dp[i][j][k][0] += dp[i-1][j-2*(k-1)*(a[i]-a[i-1])][k-1][0]*k)%mod;
      |                                     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
skyscraper.cpp:22:95: warning: value computed is not used [-Wunused-value]
   22 |     if (j >= 2*(k)*(a[i]-a[i-1])) (dp[i][j][k][0] += dp[i-1][j-2*(k)*(a[i]-a[i-1])][k][0]*2*k)%mod;
      |                                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
skyscraper.cpp:23:99: warning: value computed is not used [-Wunused-value]
   23 |     if (j >= 2*(k+1)*(a[i]-a[i-1])) (dp[i][j][k][0] += dp[i-1][j-2*(k+1)*(a[i]-a[i-1])][k+1][0]*k)%mod;
      |                                     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
skyscraper.cpp:25:99: warning: value computed is not used [-Wunused-value]
   25 |     if (j >= 2*(k-1)*(a[i]-a[i-1])) (dp[i][j][k][1] += dp[i-1][j-2*(k-1)*(a[i]-a[i-1])][k-1][0]*2)%mod;
      |                                     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
skyscraper.cpp:26:93: warning: value computed is not used [-Wunused-value]
   26 |     if (j >= 2*(k)*(a[i]-a[i-1])) (dp[i][j][k][1] += dp[i-1][j-2*(k)*(a[i]-a[i-1])][k][0]*2)%mod;
      |                                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
skyscraper.cpp:28:111: warning: value computed is not used [-Wunused-value]
   28 |     if (j >= (2*(k-1)-1)*(a[i]-a[i-1])) (dp[i][j][k][1] += dp[i-1][j-(2*(k-1)-1)*(a[i]-a[i-1])][k-1][1]*(k-1))%mod;
      |                                         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
skyscraper.cpp:29:109: warning: value computed is not used [-Wunused-value]
   29 |     if (j >= (2*(k)-1)*(a[i]-a[i-1])) (dp[i][j][k][1] += dp[i-1][j-(2*(k)-1)*(a[i]-a[i-1])][k][1]*(2*(k)-1))%mod;
      |                                       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
skyscraper.cpp:30:109: warning: value computed is not used [-Wunused-value]
   30 |     if (j >= (2*(k+1)-1)*(a[i]-a[i-1])) (dp[i][j][k][1] += dp[i-1][j-(2*(k+1)-1)*(a[i]-a[i-1])][k+1][1]*(k))%mod;
      |                                         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
skyscraper.cpp:32:105: warning: value computed is not used [-Wunused-value]
   32 |     if (j >= (2*(k-1)-1)*(a[i]-a[i-1])) (dp[i][j][k][2] += dp[i-1][j-(2*(k-1)-1)*(a[i]-a[i-1])][k-1][1])%mod;
      |                                         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
skyscraper.cpp:33:99: warning: value computed is not used [-Wunused-value]
   33 |     if (j >= (2*(k)-1)*(a[i]-a[i-1])) (dp[i][j][k][2] += dp[i-1][j-(2*(k)-1)*(a[i]-a[i-1])][k][1])%mod;
      |                                       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
skyscraper.cpp:35:111: warning: value computed is not used [-Wunused-value]
   35 |     if (j >= (2*(k-1)-2)*(a[i]-a[i-1])) (dp[i][j][k][2] += dp[i-1][j-(2*(k-1)-2)*(a[i]-a[i-1])][k-1][2]*(k-2))%mod;
      |                                         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
skyscraper.cpp:36:109: warning: value computed is not used [-Wunused-value]
   36 |     if (j >= (2*(k)-2)*(a[i]-a[i-1])) (dp[i][j][k][2] += dp[i-1][j-(2*(k)-2)*(a[i]-a[i-1])][k][2]*(2*(k)-2))%mod;
      |                                       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
skyscraper.cpp:37:109: warning: value computed is not used [-Wunused-value]
   37 |     if (j >= (2*(k+1)-2)*(a[i]-a[i-1])) (dp[i][j][k][2] += dp[i-1][j-(2*(k+1)-2)*(a[i]-a[i-1])][k+1][2]*(k))%mod;
      |                                         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 440 KB Output is correct
4 Correct 1 ms 1628 KB Output is correct
5 Correct 8 ms 17500 KB Output is correct
6 Correct 6 ms 15708 KB Output is correct
7 Correct 1 ms 3164 KB Output is correct
8 Correct 1 ms 1884 KB Output is correct
9 Correct 7 ms 16644 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2136 KB Output is correct
2 Correct 2 ms 3676 KB Output is correct
3 Correct 1 ms 1884 KB Output is correct
4 Correct 1 ms 3676 KB Output is correct
5 Correct 2 ms 3608 KB Output is correct
6 Correct 1 ms 3420 KB Output is correct
7 Correct 1 ms 1372 KB Output is correct
8 Correct 1 ms 1976 KB Output is correct
9 Correct 1 ms 2908 KB Output is correct
10 Correct 2 ms 3264 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 440 KB Output is correct
4 Correct 1 ms 1628 KB Output is correct
5 Correct 8 ms 17500 KB Output is correct
6 Correct 6 ms 15708 KB Output is correct
7 Correct 1 ms 3164 KB Output is correct
8 Correct 1 ms 1884 KB Output is correct
9 Correct 7 ms 16644 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 1 ms 2136 KB Output is correct
12 Correct 2 ms 3676 KB Output is correct
13 Correct 1 ms 1884 KB Output is correct
14 Correct 1 ms 3676 KB Output is correct
15 Correct 2 ms 3608 KB Output is correct
16 Correct 1 ms 3420 KB Output is correct
17 Correct 1 ms 1372 KB Output is correct
18 Correct 1 ms 1976 KB Output is correct
19 Correct 1 ms 2908 KB Output is correct
20 Correct 2 ms 3264 KB Output is correct
21 Correct 2 ms 4700 KB Output is correct
22 Incorrect 92 ms 164328 KB Output isn't correct
23 Halted 0 ms 0 KB -