Submission #434756

#	Time	Username	Problem	Language	Result	Execution time	Memory
434756		AriaH	Skyscraper (JOI16_skyscraper)	C++11	100 / 100	92 ms	7372 KiB

skyscraper

/** I can do this all day **/

#pragma GCC optimize("Ofast")
#pragma GCC target("avx")
#include <bits/stdc++.h>
using namespace std;

typedef long long                   ll;
typedef long double                 ld;
typedef pair<int,int>               pii;
typedef pair<ll,ll>                 pll;
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define Mp                          make_pair
#define SZ(x)			    		(int)x.size()
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io                     freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);

const int N = 1e2 + 10;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll inf = 8e18;
const int LOG = 22;
const int MXL = 1e3 + 10;

int n, L, A[N];

ll dp[2][2][2][N][MXL]; /// dp[i][left][right][j][k] -> tedad halati ke i taye aval j ta moalefe ke left left baste ast ya na va hamintor right ba sigma delta = k

ll tot;

int main()
{
	scanf("%d%d", &n, &L);
	for(int i = 1; i <= n; i ++)
	{
		scanf("%d", &A[i]);
	}
	if(n == 1) { return !printf("1"); }
	sort(A + 1, A + n + 1);
	dp[0][0][0][0][0] = 1;
	for(int i = 0; i < n; i ++)
	{
		int I = i & 1, I2 = I ^ 1;
		memset(dp[I2], 0, sizeof dp[I2]);
		for(int l = 0; l < 2; l ++)
		{
			for(int r = 0; r < 2; r ++)
			{
				for(int j = 0; j <= i; j ++)
				{
					for(int k = 0; k <= L; k ++)
					{
						if(dp[I][l][r][j][k] == 0) continue;
						ll cu = dp[I][l][r][j][k];
						int k2 = k + (2 * j - l - r) * (A[i + 1] - A[i]);
						///printf("here i = %d j = %d k = %d l = %d r = %d cu = %lld\n", i, j, k, l, r, cu);
						if(k2 > L) continue;
						if(l == 0)
						{
							if(j) dp[I2][1][r][j][k2] = (dp[I2][1][r][j][k2] + cu) % mod; /// bechasbe be left hazer L fix
							dp[I2][1][r][j + 1][k2] = (dp[I2][1][r][j + 1][k2] + cu) % mod; /// L beshe fix moalefe jadid
						}
						if(r == 0)
						{
							if(j) dp[I2][l][1][j][k2] = (dp[I2][l][1][j][k2] + cu) % mod; /// bechasbe be right hazer R fix
							dp[I2][l][1][j + 1][k2] = (dp[I2][l][1][j + 1][k2] + cu) % mod; /// R beshe fix moalefe jadid
						}
						/// moalefe jadid
						dp[I2][l][r][j + 1][k2] = (dp[I2][l][r][j + 1][k2] + cu * (j + 1 - l - r)) % mod;
						/// bechasbe be yeki
						dp[I2][l][r][j][k2] = (dp[I2][l][r][j][k2] + cu * (2 * j - l - r)) % mod;
						/// bechasbe be dota
						if(j) dp[I2][l][r][j - 1][k2] = (dp[I2][l][r][j - 1][k2] + cu * (j - 1)) % mod;
					}
				}
			}
		}
	}
	for(int k = 0; k <= L; k ++)
	{
		tot = (tot + dp[n & 1][1][1][1][k]) % mod;
	}
	printf("%lld", tot);
    return 0;
}

/** test corner cases(n = 1?) watch for overflow or minus indices **/

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:35:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |  scanf("%d%d", &n, &L);
      |  ~~~~~^~~~~~~~~~~~~~~~
skyscraper.cpp:38:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |   scanf("%d", &A[i]);
      |   ~~~~~^~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 80 / 80