Submission #414774

#	Time	Username	Problem	Language	Result	Execution time	Memory
414774		amunduzbaev	A Difficult(y) Choice (BOI21_books)	C++14	0 / 100	1366 ms	31660 KiB

books

#include "books.h"
#include <bits/stdc++.h>
#ifndef EVAL
#include "grader.cpp"
#endif

using namespace std;

#define int long long
#define i32 int32_t
#define pb push_back
#define ff first
#define ss second

template<class T> bool umin(T& a, const T b) { if(a > b) { a = b; return 1; } return 0; }
template<class T> bool umax(T& a, const T b) { if(a < b) { a = b; return 1; } return 0; }
template<int sz> using tut = array<int, sz>;

const int M = 2e5+5;
const long long inf = 1e18;
const int mod = 1e9+7;
int a[M], pref[M];

void solve(i32 n, i32 k, int A, i32 s){
	for(int i=1;i<=n;i++) a[i] = skim(i);
	set<tut<3>> ss;
	for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) ss.insert({a[i] + a[j], i, j});
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i == j) continue;
			ss.erase({a[i] + a[j], min(i, j), max(i, j)});
		}
		
		int rem = 2*A  - a[i];
		auto x = ss.upper_bound({rem, mod, mod});
		if(x != ss.begin()){ x--;
			if(a[(*x)[1]] + a[(*x)[2]] + a[i] >= A) answer({(i32)(*x)[1], (i32)(*x)[2], (i32)i});
		}
		
		for(int j=1;j<=n;j++){
			if(i == j) continue;
			ss.insert({a[i] + a[j], min(i, j), max(i, j)});
		}
	}
}


/*
void solve(i32 n, i32 k, int A, i32 s) {
	if(s < n) { impossible(); return; }
	
	for(i32 i=1;i<=n;i++) a[i] = skim(i);
	for(int i=1;i<=n;i++) pref[i] = pref[i-1] + a[i];
	int res = inf, l = -1, r = -1;
	for(int i=k;i<=n;i++){
		if(pref[i] - pref[i-k] >= A && umin(res, pref[i] - pref[i-k])) l = i-k+1, r = i;
	} if(l == -1) { impossible(); return; }
	set<pair<int, int>> ss;
	for(int i=l;i<=r;i++) ss.insert({a[i], i});
	for(int i=l-1;i>=0;i--){
		if(res <= 2*A) continue;
		int bad = -1;
		for(auto x : ss){
			if(res - x.ff + a[i] < A) break;
			bad = i;
		} if(~bad) ss.erase({a[bad], bad}), ss.insert({a[i], i}), res = res - a[bad] + a[i];
	} if(res >= A && res <= 2*A){
		vector<i32> rr;
		for(auto x : ss) rr.pb(x.ss);
		answer(rr);
	} else impossible();
	return;
}

4 3 20 5
5 10 17 25

*/

• Subtask 1: 0 / 5
• Subtask 2: 0 / 15
• Subtask 3: 0 / 10
• Subtask 4: 0 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20