oj.uz

Submission #635679

# Submission time Handle Problem Language Result Execution time Memory
635679 2022-08-26T16:13:14 Z IWTIM San (COCI17_san) C++14
48 / 120
 160 ms 10004 KB 
# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define int long long
#define pii pair <int, int>
#define pb push_back
const int N = 3e5 + 5;
int t,n,a[N],ans,g[N],sum,k;
vector <int> v[N];
void find(int pr, int sum, int k) {
	int le = 0;
	int ri = (int)v[pr].size() - 1;
	int pas = ri + 1;
	while (le <= ri) {
		int mid = (le + ri) / 2;
		if (v[pr][mid] + sum >= k) {
			pas = mid;
			ri = mid - 1;
		} else le = mid + 1;
	}
	ans += (int)v[pr].size() - pas;
}
main() {
    std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>k;
    for (int i = 0; i < n; i++) {
    	cin>>a[i]>>g[i];
	}
	for (int i = 0; i < (1<<(n/2)); i++) {
		int sum = 0, lst = -1, cur = -1, ff = 0;
		for (int j = 0; j < n/2; j++) {
		    if ((1<<j)&i && a[j] < cur) ff = 1;
			if ((1<<j)&i) lst = j, sum += g[j], cur = a[j];
			
		}
		if (ff) continue;
		if (sum >= k) ans++;
		if (lst != -1)
		if (lst != -1)
		v[lst].pb(sum);
	}
	for (int i = 0; i < n; i++) sort(v[i].begin(), v[i].end());
	for (int i = 0; i < (1<<(n / 2)); i++) {
		int sum = 0, frst = -1,ff = 0, cur = -1;
		for (int j = n / 2; j < n; j++) {
			int x = j - n / 2;
			if ((1<<x)&i && a[j] < cur) ff = 1;
			if ((1<<x)&i && frst == -1) frst = j;
			if ((1<<x)&i) sum += g[j], cur = a[j];
			
		}
		if (frst == -1 || ff) continue;
		if (sum >= k) ans++;
		for (int pr = 0; pr < n/2; pr++) {
			if (a[pr] <= a[frst]) {
				find(pr,sum, k);
			}
		}
	}
	cout<<ans<<"\n";
}

Compilation message

san.cpp:24:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   24 | main() {
      | ^~~~

Subtask #1
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB Output is correct
2 Correct 4 ms 7316 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct

Subtask #3
0 / 24.0

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

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 8068 KB Output is correct
2 Incorrect 38 ms 7508 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

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