27933 - 대회 이름 정하기

 

 

step 1

카드를 고를 수 있는 구간이 정해졌다고 해봅시다. 그럼 그 구간에는 K들과 Y들이 번갈아가며 있습니다. 각 선수들이 최선을 다해 플레이를 한다면 각 구간 안에서 가장 큰 값을 가져갈 것입니다. 

step 2

연속한 K와 Y를 K묶음, Y묶음으로 표현하겠습니다. 만약 카드를 고를 수 있는 구간 안에 묶음이 포함된다면 그 묶음 안의 최댓값만 알고 있으면 됩니다. 다른 카드는 절대 고르지 않을 것이니까요. 그럼 묶음의 일부만 포함된다면 어떻게 될까요?

 

우선 묶음의 가운데가 포함된다면 답은 YK 0입니다. 어차피 둘 다 아무것도 고르지 못합니다.

안됨

그럼 오른쪽이나 왼쪽이 포함되는 경우를 생각해 봅시다. 그럼 포함되는 영역 중 최댓값을 뽑을 것입니다. 그럼 각 위치마다

1. 내 묶음의 왼쪽에 있는 값 중 최댓값
2. 내 묶음의 오른쪽에 있는 값 중 최댓값
3. 내 묶음의 최댓값

을 저장해 두면 도움이 되겠네요.

step 3

Y묶음과 K묶음이 번갈아가며 놓여 있습니다. 만약 선택한 구간의 시작이 Y라면 그 묶음은 연대, 아니면 고대가 먹습니다.  만약 선택한 구간의 끝이 K면 그 묶음은 연대, 아니면 고대가 먹습니다. 그 가운데는 연대와 고대가 모두 먹기 때문에 승패에는 영향이 없습니다.

코드

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<vector>
#include<queue>
#include<map>
#include<string>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
long long int sum[600000];
long long int ch[600000];
long long int sc[600000];
struct data {
    long long int r, l,rp,lp,c;
}b[600000];
int main() {
    long long int n, i,m;
    scanf("%lld", &n);
    for (i = 1;i <= n;i++) {
        char x;
        scanf(" %c", &x);
        if (x == 'Y') ch[i] = 1;
    }
    for (i = 1;i <= n;i++) {
        scanf("%lld", &sc[i]);
    }
    long long int cnt = 0;
    ch[0] = -1; ch[n + 1] = -1;
    for (i = 1;i <= n;i++) {
        if (ch[i] != ch[i - 1]) {
            cnt = 0;
            b[i].lp = i;
            b[i].c = b[i - 1].c + 1;
        }
        else {
            b[i].lp = b[i - 1].lp;
            b[i].c = b[i - 1].c;
        }
        if (cnt < sc[i]) cnt = sc[i];
        b[i].l = cnt;
    }
    cnt = 0;
    for (i = n;i >= 1;i--) {
        if (ch[i] != ch[i + 1]) {
            cnt = 0;
            b[i].rp = i;
            sum[b[i].c] = b[i].l;
        }
        else {
            b[i].rp = b[i + 1].rp;
        }
        if (cnt < sc[i]) cnt = sc[i];
        b[i].r = cnt;
    }
    for (i = 1;i <= b[n].c;i++) {
        sum[i] += sum[i - 1];
    }
    scanf("%lld", &m);
    for (i = 1;i <= m;i++) {
        long long int x, y,c1=0,c2=0;
        scanf("%lld%lld", &x, &y);
        if (b[x].c == b[y].c) { printf("YK 0\n"); continue; }
        if (ch[x] == 1) c1 += b[x].r; else c2 += b[x].r;
        if (ch[y] == 0) c1 += b[y].l; else c2 += b[y].l;
        c1 += sum[b[y].c - 1] - sum[b[x].c];
        c2 += sum[b[y].c - 1] - sum[b[x].c];
        if (c1 < c2)printf("K %lld\n", c2);
        if (c1 > c2)printf("Y %lld\n", c1);
        if (c1 == c2)printf("YK %lld\n", c1);
    }
    return 0;
}