oj.uz

Submission #87847

# Submission time Handle Problem Language Result Execution time Memory
87847 2018-12-02T20:56:09 Z jasony123123 San (COCI17_san) C++11
0 / 120
 188 ms 66560 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
//using namespace __gnu_pbds;

#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define vsort(a) sort(a.begin(), a.end());
#define mp make_pair
#define v vector
#define sf scanf
#define pf printf

typedef long long ll;
typedef pair<int, int > pii;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
void io();

int N;
ll K;
int H[42];
ll G[42];

v<int> adjL[42], adjR[42];
v<ll> goldL[42], goldR[42];

void printStuff() {
	FORE(i, 0, N + 1)
		pf("%d: G = %lld, H = %d\n", i, G[i], H[i]);

	cout << N << "\n";
	cout << "L = 0 -> 2 \n";
	pf("R = 3 -> %d\n", N + 1);

	FORE(i, 0, 2) for (int j : adjL[i])
		pf("adjl: %d to %d\n", i, j);
	FORE(i, 3, N + 1) for (int j : adjR[i])
		pf("adjr: %d to %d\n", i, j);

	FOR(lh, 0, 42)
		for (int gold : goldL[lh])
			pf("gold at left: %d\n", gold);
	FOR(rh, 0, 42)
		for (int gold : goldR[rh])
			pf("gold at righ: %d\n", gold);
}


void compress() {
	map<ll, int> conv;
	FORE(i, 0, N + 1)
		conv[H[i]] = 0;
	int num = 0;
	for (auto en : conv)
		conv[en.first] = num++;
	FORE(i, 0, N + 1)
		H[i] = conv[H[i]];
}

void makeAdj() {
	assert(N >= 3);
	FORE(i, 0, 2) FORE(j, i + 1, 2)
		if (H[i] <= H[j])
			adjL[i].push_back(j);
	FORE(i, 3, N + 1) FORE(j, 3, i - 1)
		if (H[j] <= H[i])
			adjR[i].push_back(j);
}

void dfs(int i, int g, v<ll> gold[], v<int> adj[]) {
	g += G[i];
	gold[H[i]].push_back(g);
	for (int j : adj[i])
		dfs(j, g, gold, adj);
}

ll query(int lh, ll lg) { // left Hight, left Gold
	ll ans = 0;
	FOR(rh, lh, 42) {
		auto it = lower_bound(goldR[rh].begin(), goldR[rh].end(), K - lg);
		if (it != goldR[rh].end())
			ans += (int)(it - goldR[rh].begin()) + 1;
	}
	return ans;
}

int solve() {
	compress();
	makeAdj();
	dfs(0, 0, goldL, adjL);
	dfs(N + 1, 0, goldR, adjR);
	FOR(h, 0, 42) {
		vsort(goldL[h]);
		vsort(goldR[h]);
	}
	ll ans = 0;
	FOR(lh, 0, 42)
		for (int gold : goldL[lh])
			ans += query(lh, gold);
//	printStuff();
	return ans;
}

ll naive() {
	map<ll, ll> cnt[42];
	v<int> adj[42];
	cnt[N + 1][0] = 1;
	RFORE(i, N, 0)
		FOR(j, i + 1, N + 2)
			if (H[i] <= H[j]) 
				for (auto entry : cnt[j]) 
					cnt[i][min(K, entry.first + G[i])] += entry.second;
	return cnt[0][K];
}

int main() {
	io();

	cin >> N >> K;
	H[0] = 0;
	G[0] = 0;
	FORE(i, 1, N)
		cin >> H[i] >> G[i];
	H[N + 1] = 1e9 + 1;
	G[N + 1] = 0;

	if (N < 3) cout << naive() << "\n";
	else cout << solve() << "\n";
	return 0;
}


void io() {
#ifdef LOCAL_PROJECT
	freopen("input.in", "r", stdin);
	freopen("output.out", "w", stdout);
#else
	// add i/o method of specific testing system
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
}

Subtask #1
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 1276 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 174 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 158 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 188 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -