oj.uz

Submission #132212

# Submission time Handle Problem Language Result Execution time Memory
132212 2019-07-18T13:21:35 Z godwind Skyscraper (JOI16_skyscraper) C++14
100 / 100
 255 ms 31440 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 504 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 504 KB Output is correct
5 Correct 3 ms 760 KB Output is correct
6 Correct 4 ms 1148 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 2 ms 508 KB Output is correct
9 Correct 3 ms 1016 KB Output is correct
10 Correct 3 ms 548 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 888 KB Output is correct
2 Correct 3 ms 760 KB Output is correct
3 Correct 3 ms 680 KB Output is correct
4 Correct 3 ms 604 KB Output is correct
5 Correct 3 ms 632 KB Output is correct
6 Correct 3 ms 760 KB Output is correct
7 Correct 3 ms 632 KB Output is correct
8 Correct 3 ms 760 KB Output is correct
9 Correct 3 ms 888 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 504 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 504 KB Output is correct
5 Correct 3 ms 760 KB Output is correct
6 Correct 4 ms 1148 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 2 ms 508 KB Output is correct
9 Correct 3 ms 1016 KB Output is correct
10 Correct 3 ms 548 KB Output is correct
11 Correct 3 ms 888 KB Output is correct
12 Correct 3 ms 760 KB Output is correct
13 Correct 3 ms 680 KB Output is correct
14 Correct 3 ms 604 KB Output is correct
15 Correct 3 ms 632 KB Output is correct
16 Correct 3 ms 760 KB Output is correct
17 Correct 3 ms 632 KB Output is correct
18 Correct 3 ms 760 KB Output is correct
19 Correct 3 ms 888 KB Output is correct
20 Correct 3 ms 632 KB Output is correct
21 Correct 5 ms 1400 KB Output is correct
22 Correct 255 ms 31440 KB Output is correct
23 Correct 169 ms 12408 KB Output is correct
24 Correct 167 ms 16352 KB Output is correct
25 Correct 178 ms 13304 KB Output is correct
26 Correct 157 ms 12124 KB Output is correct
27 Correct 84 ms 12156 KB Output is correct
28 Correct 147 ms 15132 KB Output is correct
29 Correct 184 ms 21500 KB Output is correct
30 Correct 177 ms 13176 KB Output is correct