oj.uz

Submission #122876

# Submission time Handle Problem Language Result Execution time Memory
122876 2019-06-29T12:36:10 Z egorlifar Skyscraper (JOI16_skyscraper) C++17
100 / 100
 250 ms 19188 KB 
/*
ЗАПУСКАЕМ 
░ГУСЯ░▄▀▀▀▄░РАБОТЯГУ░░
▄███▀░◐░░░▌░░░░░░░
░░░░▌░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░▄▀▒▒▀▀▀▀▄
░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░▄▄▌▌▄▌▌░░░░░ 
 */
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
    
     
using namespace std;
template<typename T1, typename T2>inline void chkmin(T1 &x, T2 y) { if (x > y) x = y; }
template<typename T1, typename T2>inline void chkmax(T1 &x, T2 y) { if (x < y) x = y; } 
template<typename T, typename U> inline ostream &operator<< (ostream &_out, const pair<T, U> &_p) { _out << _p.first << ' ' << _p.second; return _out; }
template<typename T, typename U> inline istream &operator>> (istream &_in, pair<T, U> &_p) { _in >> _p.first >> _p.second; return _in; }
template<typename T> inline ostream &operator<< (ostream &_out, const vector<T> &_v) { if (_v.empty()) { return _out; } _out << _v.front(); for (auto _it = ++_v.begin(); _it != _v.end(); ++_it) { _out << ' ' << *_it; } return _out; }
template<typename T> inline istream &operator>> (istream &_in, vector<T> &_v) { for (auto &_i : _v) { _in >> _i; } return _in; }
template<typename T> inline ostream &operator<< (ostream &_out, const set<T> &_s) { if (_s.empty()) { return _out; } _out << *_s.begin(); for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) { _out << ' ' << *_it; } return _out; }
template<typename T> inline ostream &operator<< (ostream &_out, const multiset<T> &_s) { if (_s.empty()) { return _out; } _out << *_s.begin(); for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) { _out << ' ' << *_it; } return _out; }
template<typename T> inline ostream &operator<< (ostream &_out, const unordered_set<T> &_s) { if (_s.empty()) { return _out; } _out << *_s.begin(); for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) { _out << ' ' << *_it; } return _out; }
template<typename T> inline ostream &operator<< (ostream &_out, const unordered_multiset<T> &_s) { if (_s.empty()) { return _out; } _out << *_s.begin(); for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) { _out << ' ' << *_it; } return _out; }
template<typename T, typename U> inline ostream &operator<< (ostream &_out, const map<T, U> &_m) { if (_m.empty()) { return _out; } _out << '(' << _m.begin()->first << ": " << _m.begin()->second << ')'; for (auto _it = ++_m.begin(); _it != _m.end(); ++_it) { _out << ", (" << _it->first << ": " << _it->second << ')'; } return _out; }
template<typename T, typename U> inline ostream &operator<< (ostream &_out, const unordered_map<T, U> &_m) { if (_m.empty()) { return _out; } _out << '(' << _m.begin()->first << ": " << _m.begin()->second << ')'; for (auto _it = ++_m.begin(); _it != _m.end(); ++_it) { _out << ", (" << _it->first << ": " << _it->second << ')'; } return _out; }
#define sz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define left left228
#define right right228
#define next next228
#define rank rank228
#define prev prev228
#define y1 y1228                                                         
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define files(FILENAME) read(FILENAME), write(FILENAME)
#define pb push_back
const string FILENAME = "input";
const int MAXN = 101;
const int Mod = 1000000007;


int sum(int a, int b) {
	return (a + b >= Mod ? a + b - Mod: a + b);
}


int mul(int a, int b) {
	return (1LL * a * b) % Mod;
}

int n, m;
int a[MAXN];
int dp[MAXN][MAXN][1001][2][2];


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//read(FILENAME);
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	if (n == 1) {
		cout << 1 << endl;
		return 0;
	}
	sort(a, a + n);
	for (int i = n - 1; i >= 1; i--) {
		a[i] -= a[i - 1];
	}
	a[0] = 0;
	dp[0][0][0][0][0] = 1;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= i; j++) {
			for (int k = 0; k <= m; k++) {
				for (int l = 0; l < 2; l++) {
					for (int r = 0; r < 2; r++) {
						int cnt = dp[i][j][k][l][r];
						if (!cnt) continue;
						int nk = k + a[i] * (2 * j - l - r);
						if (nk > m) {
							continue;
						}
						if (!l) {
							int mult = j - r;
							if (i == n - 1) {
								mult += r;
							}
							dp[i + 1][j][nk][1][r] = sum(dp[i + 1][j][nk][1][r], mul(mult, cnt));
							dp[i + 1][j + 1][nk][1][r] = sum(dp[i + 1][j + 1][nk][1][r], cnt);
						}
						if (!r) {
							int mult = j - l;
							if (i == n - 1) {
								mult += l;
							}
							dp[i + 1][j][nk][l][1] = sum(dp[i + 1][j][nk][l][1], mul(mult, cnt));
							dp[i + 1][j + 1][nk][l][1] = sum(dp[i + 1][j + 1][nk][l][1], cnt);
						}
						dp[i + 1][j][nk][l][r] = sum(dp[i + 1][j][nk][l][r], mul(cnt, 2 * j - l - r));
						dp[i + 1][j + 1][nk][l][r] = sum(dp[i + 1][j + 1][nk][l][r], cnt);
						if (j > 1) {
							int mult = (j - l - r) * (j - 1);
							if (i == n - 1) {
								mult += (l & r);
							}
							dp[i + 1][j - 1][nk][l][r] = sum(dp[i + 1][j - 1][nk][l][r], mul(mult, cnt));
						}
					}
				}
 			}
		}
	} 
	int ans = 0;
	for (int i = 0; i <= m; i++) {
		ans = sum(ans, dp[n][1][i][1][1]);
	}
	cout << ans << endl;
	return 0; 		
}

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 380 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 3 ms 636 KB Output is correct
10 Correct 2 ms 632 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 632 KB Output is correct
3 Correct 3 ms 760 KB Output is correct
4 Correct 2 ms 632 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 3 ms 632 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 3 ms 760 KB Output is correct
9 Correct 3 ms 760 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 380 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 3 ms 636 KB Output is correct
10 Correct 2 ms 632 KB Output is correct
11 Correct 3 ms 760 KB Output is correct
12 Correct 3 ms 632 KB Output is correct
13 Correct 3 ms 760 KB Output is correct
14 Correct 2 ms 632 KB Output is correct
15 Correct 2 ms 504 KB Output is correct
16 Correct 3 ms 632 KB Output is correct
17 Correct 2 ms 504 KB Output is correct
18 Correct 3 ms 760 KB Output is correct
19 Correct 3 ms 760 KB Output is correct
20 Correct 3 ms 632 KB Output is correct
21 Correct 4 ms 1400 KB Output is correct
22 Correct 250 ms 19188 KB Output is correct
23 Correct 130 ms 7288 KB Output is correct
24 Correct 144 ms 10488 KB Output is correct
25 Correct 141 ms 8180 KB Output is correct
26 Correct 127 ms 7668 KB Output is correct
27 Correct 73 ms 9080 KB Output is correct
28 Correct 98 ms 10872 KB Output is correct
29 Correct 169 ms 13944 KB Output is correct
30 Correct 145 ms 8440 KB Output is correct