제출 #17539

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
17539		gs14004	케이크 (JOI13_cake)	C++14	10 / 100	1500 ms	5268 KiB

cake

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <complex>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <numeric>
#include <deque>
#include <utility>
#include <bitset>
#include <iostream>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
typedef complex<double> pnt;

int a[300005], n;
lint ret[300005];
int rotp;

lint expand(int x, int s, int e){
	int ps = x, pe = x;
	lint ret = a[x];
	for(int i=0; i<e-s; i++){
		if(ps == s || a[ps-1] < a[pe+1]){
			pe++;
			if(i%2 == 1) ret += a[pe];
		}
		else{
			ps--;
			if(i%2 == 1) ret += a[ps];
		}
	}
	return ret;
}

void solve(int s, int e, lint alt0, lint alt1){
	if(s > e) return;
	int p = min_element(a+s, a+e+1) - a;
	ret[p] = expand(p, s, e) + alt0;
	lint nalt0 = 0, nalt1 = 0;
	for(int i=p; i<=e; i++){
		if((i - s) % 2){
			nalt1 += a[i];
		}
		else{
			nalt0 += a[i];
		}
	}
	solve(s, p-1, nalt0 + alt0, nalt1 + alt1);
	nalt0 = nalt1 = 0;
	for(int i=p; i>=s; i--){
		if((e - i) % 2){
			nalt1 += a[i]; 
		}
		else{
			nalt0 += a[i];
		}
	}
	solve(p+1, e, nalt0 + alt0, nalt1 + alt1);
}

int main(){
	scanf("%d",&n);
	for(int i=0; i<n; i++){
		scanf("%d",&a[i]);
	}
	rotp = min_element(a, a+n) - a;
	rotate(a, a + rotp, a+n);
	ret[0] = a[0];
	int s = 1, e = n-1;
	for(int i=0; i<n-1; i++){
		if(a[s] < a[e]){
			if(i%2 == 1) ret[0] += a[e];
			e--;
		}
		else{
			if(i%2 == 1) ret[0] += a[s];
			s++;
		}
	}
	if(n%2 == 1) solve(1, n-1, a[0], 0);
	else solve(1, n-1, 0, a[0]); // who eats that
	rotate(ret, ret + n - rotp, ret + n);
	for(int i=0; i<n; i++){
		printf("%lld\n",ret[i]);
	}
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 90