Submission #1008568

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008568		yellowtoad	Skyscraper (JOI16_skyscraper)	C++17	20 / 100	89 ms	164408 KiB

skyscraper

#include <iostream>
#include <algorithm>
#define int long long
using namespace std;

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

signed 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 (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:22:99: warning: value computed is not used [-Wunused-value]
   22 |     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:23:95: warning: value computed is not used [-Wunused-value]
   23 |     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:24:99: warning: value computed is not used [-Wunused-value]
   24 |     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:26:99: warning: value computed is not used [-Wunused-value]
   26 |     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:27:93: warning: value computed is not used [-Wunused-value]
   27 |     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:29:111: warning: value computed is not used [-Wunused-value]
   29 |     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:30:109: warning: value computed is not used [-Wunused-value]
   30 |     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:31:109: warning: value computed is not used [-Wunused-value]
   31 |     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:33:105: warning: value computed is not used [-Wunused-value]
   33 |     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:34:99: warning: value computed is not used [-Wunused-value]
   34 |     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:36:111: warning: value computed is not used [-Wunused-value]
   36 |     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:37:109: warning: value computed is not used [-Wunused-value]
   37 |     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:38:109: warning: value computed is not used [-Wunused-value]
   38 |     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 / 5
• Subtask 2: 15 / 15
• Subtask 3: 0 / 80