Submission #167105

#	Time	Username	Problem	Language	Result	Execution time	Memory
167105		dantoh000	Hacker (BOI15_hac)	C++14	100 / 100	104 ms	13896 KiB

hac

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
int main(){
	int n; 
	scanf("%d",&n);
	int k = (n+1)/2;
	int l = (n)/2;
	//printf("%d",k);
	int a[n+1],p[n+1]; 
	a[0]= p[0] = 0;
	for (int i = 1; i <= n; i++) {
		scanf("%d",&a[i]);
		p[i] = p[i-1] + a[i];
	}
	vector<int> v;
	for (int i = 1; i <= n; i++){
		if (i >= k){
			//printf("%d %d\n",i, p[i]-p[i-k]);
			v.push_back(p[i]-p[i-k]);
		}
		else{
			//printf("%d %d-%d+%d=%d\n",i, p[n],p[i+l], p[i],p[n]-p[i+l]+p[i]);
			v.push_back(p[n]-p[i+l]+p[i]);
		}
	}
	deque<ii> dq;
	vector<int> w;
	int ans = 0;
	for (auto x : v) w.push_back(x);
	for (auto x : w) v.push_back(x);
	for (int i = 0; i < 2*n; i++){
		while (dq.size() && dq.back().first >= v[i]) dq.pop_back();
		if (dq.size() && i >= k && dq.front().second == i-k) dq.pop_front();
		dq.push_back(ii(v[i],i));
		//printf("deque contains: " );
		//for (auto x : dq) printf("(%d %d)",x.first,x.second);
		//printf("\n");
		if (i >= k) ans = max(ans,dq.front().first);
	}
	printf("%d",ans);
	
	
}

Compilation message (stderr)

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

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