제출 #106697

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
106697		tincamatei	Holiday (IOI14_holiday)	C++14	0 / 100	5099 ms	15964 KiB

holiday

#include"holiday.h"
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100000;
const long long INF = 1LL << 60;

struct FirstKStructure {
	set<pair<int, int> > data;

	void insert(int x, int i) {
		data.insert(make_pair(-x, i));
	}

	void erase(int x, int i) {
		data.erase(make_pair(-x, i));
	}

	long long getFirstK(int k) {
		int i = 0;
		long long rez = 0LL;
		for(auto it: data) {
			if(i < k)
				rez = rez - it.first;
			i++;
		}

		return rez;
	}
};

int *attraction;

bool twopointers(int n, int start, int d, long long cost) {
	FirstKStructure *str = new FirstKStructure();
	
	int l = 0;
	for(int i = 0; i < start; ++i)
		str->insert(attraction[i], i);
	for(int r = start; r < n && l <= start; ++r) {
		int k;
		long long cost2;
		str->insert(attraction[r], r);
		do {
			k = d - 2 * (r - start) - (start - l);
			if(k < 0)
				cost2 = -1;
			else
				cost2 = str->getFirstK(k);
			

			if(cost2 < cost && k <= r - l + 1) {
				str->erase(attraction[l], l);
				++l;
			} else if(cost2 >= cost)
				return true;
		} while(k <= r - l + 1 && l <= start && l <= r && cost2 < cost);
	}
	return false;
}

bool check(int n, int start, int d, long long cost) {
	bool rez = false;
	
	rez |= twopointers(n, start, d, cost);
	reverse(attraction, attraction + n);
	rez |= twopointers(n, n - start - 1, d, cost);
	reverse(attraction, attraction + n);

	return rez;
}

long long int findMaxAttraction(int n, int start, int d, int _attraction[]) {
	long long st = 0LL, dr = INF;
	
	attraction = _attraction;
	while(dr - st > 1) {
		long long mid = (st + dr) / 2;
		if(check(n, start, d, mid))
			st = mid;
		else
			dr = mid;
	}

	return st;
}

컴파일 시 표준 에러 (stderr) 메시지

grader.cpp: In function 'int main()':
grader.cpp:7:12: warning: variable 'n_s' set but not used [-Wunused-but-set-variable]
     int i, n_s;
            ^~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 23
• Subtask 3: 0 / 17
• Subtask 4: 0 / 53