oj.uz

Submission #198310

# Submission time Handle Problem Language Result Execution time Memory
198310 2020-01-25T14:45:31 Z dndhk Hacker (BOI15_hac) C++14
20 / 100
 131 ms 12380 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 0 ms 248 KB Output is correct
3 Correct 1 ms 504 KB Output is correct
4 Correct 24 ms 2800 KB Output is correct
5 Correct 51 ms 5480 KB Output is correct
6 Correct 65 ms 6500 KB Output is correct
7 Correct 76 ms 9316 KB Output is correct
8 Correct 131 ms 12380 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -