[PS] 자석 / C++ (백준 28303번)

2023 UCPC 예선 I번 문제로, 누적 합을 사용하여 쉽게 풀 수 있는 문제이다.

 

해결 방법

 SN 모양의 자석으로 누적 합을 구하며 에너지 충전량의 최댓값을 구한다. 이때, S극이 1, N극이 5라고 가정하고, S극의 소모값이 두 수의 차(4)에 K를 곱한 값보다 크다면 S극을 N-1(4)로 옮겨준다. 이외에 N-S가 1보다 크면 N극을 한 칸씩 옮겨준다. NS 모양의 자석도 똑같은 로직으로 최댓값을 구하여 자석을 배치했을 때 배터리의 에너지 변화의 최댓값을 구한다.

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cmath>
using namespace std;
int d[500001], rd[5000001];

int main()
{
	int nn, k, s=1, n=2, answer=-2e9, c, des, rn;
	scanf("%d %d", &nn, &k);
	rn = nn;
	for (int i = 1; i <= nn; i++)scanf("%d", &d[i]);
	for (int i = 1; i <= nn; i++)rd[rn--] = d[i];
	while (1) {
		if (n == nn + 1)break;
		c = d[n] - d[s] - (n - s) * k;
		if (answer < c)answer = c;
		if (n - s == 1)n++;
		else {
			des = n - 1;
			if (d[s] - d[des] + (des - s) * k > 0) {
				s = des;
			}
			else {
				n++;
			}
		}
	}
	s = 1; n = 2;
	while (1) {
		if (n == nn + 1)break;
		c = rd[n] - rd[s] - (n - s) * k;
		if (answer < c)answer = c;
		if (n - s == 1)n++;
		else {
			des = n - 1;
			if (rd[s] - rd[des] + (des - s) * k > 0) {
				s = des;
			}
			else {
				n++;
			}
		}
	}
	printf("%d\n", answer);
	return 0;
}