Submission #31736

#	Time	Username	Problem	Language	Result	Execution time	Memory
31736		kdh9949	Hacker (BOI15_hac)	C++14	100 / 100	186 ms	14112 KiB

hac

#include <bits/stdc++.h>
using namespace std;

const int MN = 500005, sz = 1048576, inf = int(2e9) + 5;
struct Seg{
	int dat[2 * sz];
	void ini(){ fill(dat + 1, dat + 2 * sz, inf); }
	void upd(int x, int v){
		x += sz; dat[x] = v;
		for(x /= 2; x; x /= 2) dat[x] = min(dat[2 * x], dat[2 * x + 1]);
	}
	int get(int s, int e){
		int ret = inf;
		for(s += sz, e += sz; s <= e; s /= 2, e /= 2){
			if(s % 2 == 1) ret = min(ret, dat[s++]);
			if(e % 2 == 0) ret = min(ret, dat[e--]);
		}
		return ret;
	}
} S;

int n, m, s[2 * MN], ans;

int main(){
	scanf("%d", &n);
	m = (n + 1) / 2;
	for(int i = 1; i <= n; i++){
		scanf("%d", s + i);
		s[n + i] = s[i];
	}
	S.ini();
	for(int i = 2; i <= 2 * n; i++) s[i] += s[i - 1];
	for(int i = 0; i + m <= 2 * n; i++) S.upd(i, s[i + m] - s[i]);
	for(int i = m - 1; i + m <= 2 * n; i++) ans = max(ans, S.get(i - m + 1, i));
	printf("%d\n", ans);
}

Compilation message (stderr)

hac.cpp: In function 'int main()':
hac.cpp:25:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
hac.cpp:28:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", s + i);
                     ^

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