Submission #198310

#	Time	Username	Problem	Language	Result	Execution time	Memory
198310		dndhk	Hacker (BOI15_hac)	C++14	20 / 100	131 ms	12380 KiB

hac

#include <bits/stdc++.h>

#define pb push_back

using namespace std;

const int MAX_N = 500000;

typedef pair<int, int> pii;

int N;
int arr[MAX_N+1], sum[MAX_N+1];
int c[MAX_N+1];

vector<pii> vt;

int main(){
	scanf("%d", &N);
	for(int i=1; i<=N; i++){
		scanf("%d", &arr[i]);
		sum[i] = sum[i-1] + arr[i];
	}
	for(int i=1; i<=N; i++){
		if(i+(N/2)-1<=N){
			c[i] = sum[i+(N/2)-1] - sum[i-1];
		}else{
			c[i] = sum[N] - sum[i-1] + sum[(i+(N/2)-1)%N];
		}
		vt.pb({c[i], i});
	}
	sort(vt.begin(), vt.end());
	int s = vt.back().second, e = (s+(N/2)-2)%N+1;
	vt.pop_back();
	while(!vt.empty()){
		int ns = vt.back().second, ne = (ns+(N/2)-2)%N+1;
		if(ns<=ne){
			if(s<=e){
				s = max(s, ns);
				e = min(e, ne);
				if(s>e)	break;
			}else{
				if(ns>=s){
					s = max(ns, s);
					e = ne;
					if(s>e)	break;
				}else{
					e = min(e, ne);
					s = ns;
					if(s>e)	break;
				}
			}
		}else{
			if(s<=e){
				if(ns<=s){
					s = max(ns, s);
					if(s>e)	break;
				}else{
					e = min(e, ne);
					if(s>e)	break;
				}
			}else{
				s = max(ns, s);
				e = min(ne, e);
			}
		}
		vt.pop_back();
	}
	printf("%d\n", sum[N] - vt.back().first);

}

Compilation message (stderr)

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

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