oj.uz

Submission #132214

# Submission time Handle Problem Language Result Execution time Memory
132214 2019-07-18T13:23:15 Z godwind Skyscraper (JOI16_skyscraper) C++17
100 / 100
 254 ms 31324 KB 
#pragma GCC optimize("Ofast")
/*#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <cstdio>
#include <math.h>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
#include <deque>
#include <random>
#include <iomanip>
#include <bitset>
                        
using namespace std;
                        
template<typename T> void uin(T &a, T b) {
    if (b < a) {
        a = b;
    }
}
                        
template<typename T> void uax(T &a, T b) {
    if (b > a) {
        a = b;
    }
}
  
#define int long long
#define ghost signed
#define left left228
#define right right228
#define prev prev228
#define list list228

const int MOD = 1e9 + 7;

int mod(int x) {
	x %= MOD;
	if (x < 0) x += MOD;
	return x;
}

void add(int &x, int y) {
	x += y;
	if (x >= MOD) x -= MOD;
}

int a[105];
int dp[105][105][2005][2][2];

ghost main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) cin >> a[i];
	sort(a + 1, a + n + 1);
	if (n == 1) {
		cout << 1 << '\n';
		return 0;
	}
    if (n == 2) {
        if (a[2] - a[1] <= m) {
            cout << 2 << '\n';
        } else {
            cout << 0 << '\n';
        }
        return 0;
    }
	dp[1][1][2 * (a[2] - a[1])][0][0] = 1;
	dp[1][0][a[2] - a[1]][1][0] = 1;
	dp[1][0][a[2] - a[1]][0][1] = 1;
	a[n + 1] = a[n];
	for (int i = 1; i < n; ++i) {
		for (int j = 0; j <= i; ++j) {
			for (int sum = 0; sum <= m; ++sum) {
				for (int first = 0; first < 2; ++first) {
					for (int last = 0; last < 2; ++last) {
						if (!dp[i][j][sum][first][last]) continue;
                        int d = a[i + 2] - a[i + 1];
                        int DP = dp[i][j][sum][first][last];
                      add(dp[i + 1][j + 1][sum + (2 * (j + 1) + first + last) * d][first][last], DP); // create new component
                        add(dp[i + 1][j][sum + (2 * j + first + last) * d][first][last], mod((2 * j + first + last) * DP)); // add to component
                        if (!first) {
                            add(dp[i + 1][j][sum + (2 * j + 1 + last) * d][1][last], DP); // make first component
                            if (j) {
                                // cout << "dp[" << i + 1 << "][" << j - 1 << "][" << sum + (2 * (j - 1) + 1 + last) 
                                add(dp[i + 1][j - 1][sum + (2 * (j-1) + 1 + last) * d][1][last], mod(j * DP)); // make first component and merge with previous
                            }
                        } else if (j) {
                            add(dp[i + 1][j - 1][sum + (2 * (j - 1) + first + last) * d][first][last], mod(j * DP)); // merge some component with first
                        }
                        if (!last) {
                            add(dp[i + 1][j][sum + (2 * j + first + 1) * d][first][1], DP); // make last component
                            if (j) {
                                add(dp[i + 1][j - 1][sum + (2 * (j - 1) + first + 1) * d][first][1], mod(j * DP)); // make last component and merge with previous
                            }
                        } else if (j) {
                            add(dp[i + 1][j - 1][sum + (2 * (j - 1) + first + last) * d][first][last], mod(j * DP)); // merge some component with last
                        }
                        if (j > 1) {
                            add(dp[i + 1][j - 1][sum + (2 * (j-1) + first + last) * d][first][last], mod((j-1) * mod(j * DP))); // merge 2 components using us
                        }
					}
				}
			}
		}
	}
    int res = 0;
	for (int w = 0; w <= m; ++w) {
		add(res, dp[n - 1][0][w][1][1]);
		add(res, dp[n - 1][0][w][1][0]);
		add(res, dp[n - 1][0][w][0][1]);
	}
	cout << res << '\n';
    return 0;
} // kek ;

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 632 KB Output is correct
6 Correct 3 ms 1144 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 4 ms 1016 KB Output is correct
10 Correct 2 ms 500 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 760 KB Output is correct
2 Correct 3 ms 760 KB Output is correct
3 Correct 3 ms 760 KB Output is correct
4 Correct 3 ms 632 KB Output is correct
5 Correct 3 ms 632 KB Output is correct
6 Correct 3 ms 760 KB Output is correct
7 Correct 2 ms 632 KB Output is correct
8 Correct 3 ms 760 KB Output is correct
9 Correct 3 ms 1020 KB Output is correct
10 Correct 3 ms 632 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 632 KB Output is correct
6 Correct 3 ms 1144 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 4 ms 1016 KB Output is correct
10 Correct 2 ms 500 KB Output is correct
11 Correct 3 ms 760 KB Output is correct
12 Correct 3 ms 760 KB Output is correct
13 Correct 3 ms 760 KB Output is correct
14 Correct 3 ms 632 KB Output is correct
15 Correct 3 ms 632 KB Output is correct
16 Correct 3 ms 760 KB Output is correct
17 Correct 2 ms 632 KB Output is correct
18 Correct 3 ms 760 KB Output is correct
19 Correct 3 ms 1020 KB Output is correct
20 Correct 3 ms 632 KB Output is correct
21 Correct 5 ms 1528 KB Output is correct
22 Correct 254 ms 31324 KB Output is correct
23 Correct 171 ms 12352 KB Output is correct
24 Correct 167 ms 16404 KB Output is correct
25 Correct 178 ms 13276 KB Output is correct
26 Correct 154 ms 12108 KB Output is correct
27 Correct 79 ms 12156 KB Output is correct
28 Correct 104 ms 15096 KB Output is correct
29 Correct 185 ms 21368 KB Output is correct
30 Correct 177 ms 13204 KB Output is correct