oj.uz

Submission #260021

# Submission time Handle Problem Language Result Execution time Memory
260021 2020-08-09T00:55:09 Z racsosabe Hacker (BOI15_hac) C++14
20 / 100
 94 ms 27000 KB 
#include<bits/stdc++.h>
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define ri(x) scanf("%d",&(x))
#define ri2(x,y) scanf("%d %d",&(x),&(y))
#define ri3(x,y,z) scanf("%d %d %d",&(x),&(y),&(z))
#define rll(x) scanf("%lld",&(x))
#define rll2(x,y) scanf("%lld %lld",&(x),&(y))
#define rll3(x,y,z) scanf("%lld %lld %lld",&(x),&(y),&(z))
#define gc(x) ((x) = getchar())
using namespace::std;

const long double PI = acos(-1);
const long long MOD = 1000000000 +7;

typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<ll,pll> tll;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<pll> vpll;
typedef vector<tll> vtll;
typedef vector<string> vs;
typedef set<int> si;
typedef set<ii> sii;
typedef set<iii> siii;

ll gcd(ll a, ll b){ return b==0?a:gcd(b,a%b);}

ll add(ll a, ll b, ll m = MOD){
	if(a >= m) a %= m;
	if(b >= m) b %= m;
	if(a < 0) a += m;
	if(b < 0) b += m;
	ll res = a+b;
	if(res >= m or res <= -m) res %= m;
	if(res < 0) res += m;
	return res;
}

ll mul(ll a, ll b, ll m = MOD){
	if(a >= m) a %= m;
	if(b >= m) b %= m;
	if(a < 0) a += m;
	if(b < 0) b += m;
	ll res = a*b;
	if(res >= m or res <= -m) res %= m;
	if(res < 0) res += m;
	return res;
}

ll pow_mod(ll a, ll b, ll m = MOD){
	ll res = 1LL;
	a = a%m;
	while(b){
		if(b&1) res = mul(res,a,m);
		b >>= 1;
		a = mul(a,a,m);
	}
	return res;
}

ll fastexp(ll a, ll b){
	ll res = 1LL;
	while(b){
		if(b&1) res = res*a;
		b >>= 1;
		a *= a;
	}
	return res;
}

int gcdExtendido(int a, int b, int *x, int *y){
	if(a == 0){
		*x = 0;
		*y = 1;
		return b;
	}
	int x1, y1;
	int gcd = gcdExtendido(b%a,a,&x1,&y1);
	
	*x = y1-(b/a)*x1;
	*y = x1;
	return gcd;
}

int modInverso(int a, int m){
	int x, y;
	int g = gcdExtendido(a,m,&x,&y);
	if(g!=1) return -1;
	else return (x%m + m)%m;
}

/****************************************
*************P*L*A*N*T*I*L*L*A************
*****************************************/

const int N = 1500000+5;

int n;
int a[N];
ll ac[N];
int len[2];
int res[N];
int st1[2][N];
int st2[2][N];

void insert(int x){
	len[0]++;
	st1[0][len[0]] = x;
	st1[1][len[0]] = min(st1[1][len[0]-1], x);
}

void remove(){
	if(!len[1]){
		for(int j = len[0]; j >= 1; j--){
			len[1]++;
			int x = st1[0][j];
			st2[0][len[1]] = x;
			st2[1][len[1]] = min(x, st2[1][len[1]-1]);
		}
		len[0] = 0;
	}
	len[1] -= 1;
}

int getMin(){
	return min(st2[1][len[1]], st1[1][len[0]]);
}

int main(){
	ri(n);
	for(int i = 1; i <= n; i++){
		ri(a[i]);
		ac[i] = ac[i-1] + a[i];
	}
	for(int i = n+1; i <= n+n+n; i++){
		a[i] = a[i - n];
		ac[i] = ac[i - 1] + a[i];
	}
	int moves = (n + 1) / 2;
	for(int i = 1; i + moves - 1 <= n+n; i++){
		res[i] = ac[i + moves - 1] - ac[i - 1];
	}
	int ans = 0;
	st1[0][0] = st2[0][0] = st1[1][0] = st2[1][0] = 2e9;
	for(int i = n + 2 - moves; i <= n; i++){
		insert(res[i]);
	}
	for(int i = n + 1; i <= n + n; i++){
		insert(res[i]);
		if(i - moves >= n + 2 - moves) remove();
		ans = max(ans, getMin());
	}
	printf("%d\n", ans);
	return 0;
}

Compilation message

hac.cpp: In function 'int main()':
hac.cpp:6:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define ri(x) scanf("%d",&(x))
               ~~~~~^~~~~~~~~~~
hac.cpp:138:2: note: in expansion of macro 'ri'
  ri(n);
  ^~
hac.cpp:6:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define ri(x) scanf("%d",&(x))
               ~~~~~^~~~~~~~~~~
hac.cpp:140:3: note: in expansion of macro 'ri'
   ri(a[i]);
   ^~

Subtask #1
0 / 20.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Incorrect 1 ms 384 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 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 2 ms 640 KB Output is correct
4 Correct 14 ms 4608 KB Output is correct
5 Correct 33 ms 11000 KB Output is correct
6 Correct 44 ms 13688 KB Output is correct
7 Correct 53 ms 16376 KB Output is correct
8 Correct 94 ms 27000 KB Output is correct

Subtask #4
0 / 40.0

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