Submission #791796

#	Time	Username	Problem	Language	Result	Execution time	Memory
791796		lovrot	Hacker (BOI15_hac)	C++17	100 / 100	54 ms	8140 KiB

hac

#include <cstdio> 
#include <queue>
#include <deque>

using namespace std; 

typedef long long ll;

const int N = 5e5 + 10;
const int oo = 2e9 + 10;

int n, V[N];

char B[N];
int S[N];

deque<int> Q;

void add(int x, deque<int> &A) {
	while(!A.empty() && A.back() > x) A.pop_back();
	A.push_back(x);
}

void pop(int x, deque<int> &A) {
	if(!A.empty() && A.front() == x) A.pop_front();
}

int get(deque<int> &A) {
	return A.empty() ? -1 : A.front(); 
}

int main() {
	scanf("%d", &n);
	int sum = 0, _sum = 0;
	for(int i = 0; i < n; ++i) { 
		scanf("%d", V + i); 
		sum += V[i]; 
		if(i < n / 2) _sum += V[i];
	}
	for(int i = n / 2 - 1; B[i] == 0;) {
		S[i] = sum - _sum;
		B[i] = 1;
		i = (i + 1) % n;
		_sum += V[i]; 
		_sum -= V[(i - n / 2 + n) % n];
	}
	for(int i = n / 2 - 1; i < n - 1; ++i)	add(S[i], Q);
	int ans = -oo;
	for(int i = n - 1; B[i] != 2;) {
		ans = max(ans, get(Q));
		B[i] = 2;
		pop(S[(i - (n + 1) / 2 + n) % n], Q);
		i = (i + 1) % n;
		add(S[(i - 1 + n) % n], Q); 
	}
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

hac.cpp: In function 'int main()':
hac.cpp:33:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
hac.cpp:36:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |   scanf("%d", V + i);
      |   ~~~~~^~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 40 / 40