oj.uz

Submission #35377

# Submission time Handle Problem Language Result Execution time Memory
35377 2017-11-21T14:24:01 Z RockyB San (COCI17_san) C++14
120 / 120
 146 ms 20356 KB 
/// In The Name Of God

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,sse3,sse4,popcnt,abm,mmx")

#include <bits/stdc++.h>

#define f first
#define s second

#define pb push_back
#define pp pop_back
#define mp make_pair

#define sz(x) (int)x.size()
#define sqr(x) ((x) * 1ll * (x))
#define all(x) x.begin(), x.end()

#define Kazakhstan ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);

#define nl '\n'
#define ioi exit(0);

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int N = (int)5e5 + 7, inf = (int)1e9 + 7, mod = (int)1e9 + 7;
const ll linf = (ll)1e18 + 7;
const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1}, dy[] = {0, 1, 0, -1, 1, -1, 1, -1};

using namespace std;

ll n, k;
ll h[N], g[N];

struct slow {
	ll rec(int v = 1, ll sum = 0, ll last = -1) {
		if (v > n) {
			if (sum >= k) return 1;
			return 0;
		}
		ll res = rec(v + 1, sum, last);
		if (h[v] >= last) res += rec(v + 1, sum + g[v], h[v]);
		return res;
	}
	void solve() {
		cout << rec();
		ioi
	}
} s1;

namespace notslow {

	struct go {
		vector <ll> s;

		void ins(ll x) {
			s.pb(x);
		}
		void build() {
			sort(all(s));
		}
		ll get(ll x) {
			return s.end() - lower_bound(all(s), x);
		}
	} t[44];

	int mid;
	ll ans;
	void rec(int v = mid, ll sum = 0, int last = -1, int start = -1) {
		if (v > n) {
			if (sum >= k) ans++;
			if (last != -1) t[start].ins(sum);
			return;
		}
		rec(v + 1, sum, last, start);
		if (h[v] >= last) {
			if (last == -1) rec(v + 1, sum + g[v], h[v], v);
			else rec(v + 1, sum + g[v], h[v], start);
		}
	}
	ll rec1(int v = 1, ll sum = 0, int last = -1) {
		if (v == mid) {
			if (last == -1) return 0;
			ll res = (sum >= k);
			for (int j = mid; j <= n; j++) {
				if (last <= h[j]) res += t[j].get(k - sum);
			}
			return res;
		}
		ll res = rec1(v + 1, sum, last);
		if (h[v] >= last) res += rec1(v + 1, sum + g[v], h[v]);
		return res;
	}
	void solve() {
		mid = n >> 1;
		rec();
		for (int i = mid; i <= n; i++) {
			t[i].build();
		}
		cout << ans + rec1();
		ioi
	}
};

int main() {
	#ifdef IOI2018
		freopen ("in.txt", "r", stdin);
		freopen ("D.out", "w", stdout);
	#endif
	Kazakhstan
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> h[i] >> g[i];
	}
	if (n <= 20) s1.solve();
	notslow :: solve();
	ioi
}

Subtask #1
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 9992 KB Output is correct
2 Correct 0 ms 9992 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 9992 KB Output is correct
2 Correct 0 ms 9992 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 11384 KB Output is correct
2 Correct 0 ms 10152 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 13120 KB Output is correct
2 Correct 3 ms 10136 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 20356 KB Output is correct
2 Correct 13 ms 10708 KB Output is correct