oj.uz

Submission #102599

# Submission time Handle Problem Language Result Execution time Memory
102599 2019-03-26T07:03:29 Z Minnakhmetov Skyscraper (JOI16_skyscraper) C++14
20 / 100
 2000 ms 474924 KB 
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <cstring>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
#pragma warning(disable : 4996)

const int N = 101, S = 2e5 + 1, MOD = 1e9 + 7;
int a[N], b[N], dp[2][3][N][S];

void f(int &a, int b) {
	a += b;
	while (a >= MOD)
		a -= MOD;
}

signed main() {
#ifdef HOME
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n, l;
	cin >> n >> l;

	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}

	sort(a, a + n);
	reverse(a, a + n);

	for (int i = 0; i < n; i++) {
		a[i] -= a[n - 1];
	}

	for (int i = n - 1; i >= 0; i--) {
		b[i] += b[i + 1] + a[i];
	}


	dp[1][0][0][0] = 1;
	dp[1][2][0][a[0] + a[0]] = 1;
	dp[1][1][0][a[0]] = 2;
	
	for (int i = 1, q = 1; i < n; i++, q ^= 1) {
		memset(dp[q ^ 1], 0, sizeof(dp[q ^ 1]));
		int mx = b[i + 1] * 2 + l;
		for (int x = 0; x < 3; x++) {
			for (int j = 0; j < i; j++) {
				for (int k = 0; k <= (a[i - 1] << 1); k++) {
					if (dp[q][x][j][k]) {
						int cur = dp[q][x][j][k];
						if (x) {
							int cur2 = cur * x;
							if (cur2 >= MOD)
								cur2 -= MOD;
							f(dp[q ^ 1][x - 1][j][k - a[i]], cur2);
							f(dp[q ^ 1][x][j][k], cur2);
							if (k + a[i] <= mx)
								f(dp[q ^ 1][x - 1][j + 1][k + a[i]], cur2);
							if (k + a[i] + a[i] <= mx)
								f(dp[q ^ 1][x][j + 1][k + a[i] + a[i]], cur2);
						}
						cur = cur * (ll)j % MOD;
						if (j) {
							int cur2 = cur + cur;
							if (cur2 >= MOD)
								cur2 -= MOD; 
							f(dp[q ^ 1][x][j][k], cur2);
							if (k + a[i] + a[i] <= mx)
								f(dp[q ^ 1][x][j + 1][k + a[i] + a[i]], cur);
							f(dp[q ^ 1][x][j - 1][k - a[i] - a[i]], cur);
						}
						
					}
				}
			}
		}
		a[i] += a[i - 1];
	}
	

	int ans = 0;
	
	for (int i = 0; i <= l; i++) {
		f(ans, dp[n & 1][0][0][i]);
	}

	cout << ans;
	
	return 0;
}

Compilation message

skyscraper.cpp:41:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning(disable : 4996)

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 187 ms 237620 KB Output is correct
3 Correct 368 ms 474716 KB Output is correct
4 Correct 564 ms 474844 KB Output is correct
5 Correct 646 ms 474800 KB Output is correct
6 Correct 659 ms 474844 KB Output is correct
7 Correct 644 ms 474744 KB Output is correct
8 Correct 639 ms 474840 KB Output is correct
9 Correct 670 ms 474872 KB Output is correct
10 Correct 663 ms 474760 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 896 ms 474676 KB Output is correct
2 Correct 1063 ms 474752 KB Output is correct
3 Correct 1059 ms 474784 KB Output is correct
4 Correct 1079 ms 474760 KB Output is correct
5 Correct 968 ms 474744 KB Output is correct
6 Correct 976 ms 474820 KB Output is correct
7 Correct 988 ms 474744 KB Output is correct
8 Correct 1002 ms 474744 KB Output is correct
9 Correct 1026 ms 474872 KB Output is correct
10 Correct 1002 ms 474924 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 187 ms 237620 KB Output is correct
3 Correct 368 ms 474716 KB Output is correct
4 Correct 564 ms 474844 KB Output is correct
5 Correct 646 ms 474800 KB Output is correct
6 Correct 659 ms 474844 KB Output is correct
7 Correct 644 ms 474744 KB Output is correct
8 Correct 639 ms 474840 KB Output is correct
9 Correct 670 ms 474872 KB Output is correct
10 Correct 663 ms 474760 KB Output is correct
11 Correct 896 ms 474676 KB Output is correct
12 Correct 1063 ms 474752 KB Output is correct
13 Correct 1059 ms 474784 KB Output is correct
14 Correct 1079 ms 474760 KB Output is correct
15 Correct 968 ms 474744 KB Output is correct
16 Correct 976 ms 474820 KB Output is correct
17 Correct 988 ms 474744 KB Output is correct
18 Correct 1002 ms 474744 KB Output is correct
19 Correct 1026 ms 474872 KB Output is correct
20 Correct 1002 ms 474924 KB Output is correct
21 Execution timed out 2076 ms 474624 KB Time limit exceeded
22 Halted 0 ms 0 KB -