oj.uz

Submission #35663

# Submission time Handle Problem Language Result Execution time Memory
35663 2017-11-27T14:04:51 Z UncleGrandpa925 Skyscraper (JOI16_skyscraper) C++14
20 / 100
 2000 ms 100744 KB 
/*input
2 6
10 4


4 10
3 6 2 9
8 35
3 7 1 5 10 2 11 6
3 10
2 3 6 9
*/
#include <bits/stdc++.h>
using namespace std;
#define sp ' '
#define endl '\n'
#define fi first
#define se second
#define mp make_pair
#define int long long
#define N
#define bit(x,y) ((x>>y)&1LL)
#define na(x) (#x) << ":" << x
ostream& operator << (ostream &os, vector<int>&x) {
	for (int i = 0; i < x.size(); i++) os << x[i] << sp;
	return os;
}
ostream& operator << (ostream &os, pair<int, int> x) {
	cout << x.fi << sp << x.se << sp;
	return os;
}
ostream& operator << (ostream &os, vector<pair<int, int> >&x) {
	for (int i = 0; i < x.size(); i++) os << x[i] << endl;
	return os;
}

int n, lim;
vector<int> a;
map<int, int> dp[105][105][2][2];
const int mod = 1e9 + 7;
int cal(int pos, int numcc, bool loc, bool roc, int diff) {
	if (pos == n) {
		if (numcc != 1 || !loc || !roc) return 0;
		if (diff <= lim && numcc == 1 && loc && roc) return 1;
		return 0;
	}
	if (dp[pos][numcc][loc][roc].find(diff) != dp[pos][numcc][loc][roc].end()) {
		return dp[pos][numcc][loc][roc][diff];
	}
	int &ret = dp[pos][numcc][loc][roc][diff];
	// make new
	ret += cal(pos + 1, numcc + 1, loc, roc, diff - 2 * a[pos]) * (numcc + 1 - loc - roc);
	// make new loc
	if (!loc)
		ret += cal(pos + 1, numcc + 1, 1, roc, diff - a[pos]);
	// make new roc
	if (!roc)
		ret += cal(pos + 1, numcc + 1, loc, 1, diff - a[pos]);
	if (numcc) {
		// push front
		ret += cal(pos + 1, numcc, loc, roc, diff) * (numcc - loc);
		// push back
		ret += cal(pos + 1, numcc, loc, roc, diff) * (numcc - roc);
		// connect
		if (numcc >= 2) ret += cal(pos + 1, numcc - 1, loc, roc, diff + a[pos] * 2) * (numcc - 1);
		// push front loc
		if (!loc) ret += cal(pos + 1, numcc, 1, roc, diff + a[pos]);
		// push back roc
		if (!roc) ret += cal(pos + 1, numcc, loc, 1, diff + a[pos]);

	}
	ret %= mod;
	return ret;
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> lim;
	if (n == 1) {
		cout << 1 << endl;
		exit(0);
	}
	for (int i = 1; i <= n; i++) {
		int t; cin >> t;
		a.push_back(t);
	}
	sort(a.begin(), a.end());
	cout << cal(0, 0, 0, 0, 0) << endl;
}

Compilation message

skyscraper.cpp: In function 'std::ostream& operator<<(std::ostream&, std::vector<long long int>&)':
skyscraper.cpp:25:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < x.size(); i++) os << x[i] << sp;
                    ^
skyscraper.cpp: In function 'std::ostream& operator<<(std::ostream&, std::vector<std::pair<long long int, long long int> >&)':
skyscraper.cpp:33:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < x.size(); i++) os << x[i] << endl;
                    ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4252 KB Output is correct
2 Correct 0 ms 4252 KB Output is correct
3 Correct 0 ms 4252 KB Output is correct
4 Correct 0 ms 4252 KB Output is correct
5 Correct 3 ms 4780 KB Output is correct
6 Correct 3 ms 4780 KB Output is correct
7 Correct 3 ms 4648 KB Output is correct
8 Correct 3 ms 4384 KB Output is correct
9 Correct 6 ms 4780 KB Output is correct
10 Correct 0 ms 4384 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4648 KB Output is correct
2 Correct 73 ms 8872 KB Output is correct
3 Correct 3 ms 5176 KB Output is correct
4 Correct 83 ms 9004 KB Output is correct
5 Correct 99 ms 10060 KB Output is correct
6 Correct 39 ms 7288 KB Output is correct
7 Correct 19 ms 6100 KB Output is correct
8 Correct 6 ms 5308 KB Output is correct
9 Correct 13 ms 5308 KB Output is correct
10 Correct 53 ms 7948 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4252 KB Output is correct
2 Correct 0 ms 4252 KB Output is correct
3 Correct 0 ms 4252 KB Output is correct
4 Correct 0 ms 4252 KB Output is correct
5 Correct 3 ms 4780 KB Output is correct
6 Correct 3 ms 4780 KB Output is correct
7 Correct 3 ms 4648 KB Output is correct
8 Correct 3 ms 4384 KB Output is correct
9 Correct 6 ms 4780 KB Output is correct
10 Correct 0 ms 4384 KB Output is correct
11 Correct 3 ms 4648 KB Output is correct
12 Correct 73 ms 8872 KB Output is correct
13 Correct 3 ms 5176 KB Output is correct
14 Correct 83 ms 9004 KB Output is correct
15 Correct 99 ms 10060 KB Output is correct
16 Correct 39 ms 7288 KB Output is correct
17 Correct 19 ms 6100 KB Output is correct
18 Correct 6 ms 5308 KB Output is correct
19 Correct 13 ms 5308 KB Output is correct
20 Correct 53 ms 7948 KB Output is correct
21 Correct 1936 ms 69064 KB Output is correct
22 Execution timed out 2000 ms 100744 KB Execution timed out
23 Halted 0 ms 0 KB -