oj.uz

Submission #434756

# Submission time Handle Problem Language Result Execution time Memory
434756 2021-06-21T17:27:52 Z AriaH Skyscraper (JOI16_skyscraper) C++11
100 / 100
 92 ms 7372 KB 
/** 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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 3 ms 7244 KB Output is correct
3 Correct 4 ms 7244 KB Output is correct
4 Correct 5 ms 7244 KB Output is correct
5 Correct 5 ms 7244 KB Output is correct
6 Correct 5 ms 7244 KB Output is correct
7 Correct 5 ms 7244 KB Output is correct
8 Correct 5 ms 7252 KB Output is correct
9 Correct 6 ms 7244 KB Output is correct
10 Correct 5 ms 7244 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7244 KB Output is correct
2 Correct 10 ms 7244 KB Output is correct
3 Correct 7 ms 7244 KB Output is correct
4 Correct 9 ms 7372 KB Output is correct
5 Correct 9 ms 7244 KB Output is correct
6 Correct 7 ms 7244 KB Output is correct
7 Correct 7 ms 7252 KB Output is correct
8 Correct 6 ms 7212 KB Output is correct
9 Correct 7 ms 7244 KB Output is correct
10 Correct 7 ms 7244 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 3 ms 7244 KB Output is correct
3 Correct 4 ms 7244 KB Output is correct
4 Correct 5 ms 7244 KB Output is correct
5 Correct 5 ms 7244 KB Output is correct
6 Correct 5 ms 7244 KB Output is correct
7 Correct 5 ms 7244 KB Output is correct
8 Correct 5 ms 7252 KB Output is correct
9 Correct 6 ms 7244 KB Output is correct
10 Correct 5 ms 7244 KB Output is correct
11 Correct 6 ms 7244 KB Output is correct
12 Correct 10 ms 7244 KB Output is correct
13 Correct 7 ms 7244 KB Output is correct
14 Correct 9 ms 7372 KB Output is correct
15 Correct 9 ms 7244 KB Output is correct
16 Correct 7 ms 7244 KB Output is correct
17 Correct 7 ms 7252 KB Output is correct
18 Correct 6 ms 7212 KB Output is correct
19 Correct 7 ms 7244 KB Output is correct
20 Correct 7 ms 7244 KB Output is correct
21 Correct 14 ms 7372 KB Output is correct
22 Correct 92 ms 7244 KB Output is correct
23 Correct 61 ms 7208 KB Output is correct
24 Correct 71 ms 7244 KB Output is correct
25 Correct 69 ms 7244 KB Output is correct
26 Correct 59 ms 7244 KB Output is correct
27 Correct 52 ms 7244 KB Output is correct
28 Correct 53 ms 7244 KB Output is correct
29 Correct 78 ms 7244 KB Output is correct
30 Correct 70 ms 7244 KB Output is correct