10740번: ACM

https://www.acmicpc.net/problem/10740


$O(n)$

s(p,q): p번째 사람의 배열중 [1,q] 합
1,2,3 번째 사람이 하나씩 구간을 지정했다치자. ex) 첫 번째 [1,3], 두 번째 [4,5], 세 번째 [6,7]
각 구간이 순서대로 [1,i], [i+1,j], [j+1,n] 으로 지정 되어 있다면 이것이 나타내는 난이도 합은
r=s(3,n)-s(3,j) + s(2,j)-s(2,i) +s(1,i) 일 것이다.
주어진 문제는 이러한 r중에 가능한 최솟값을 찾는 것이 목표이다.
이를 해결하기 위해 j가 정해졌을 때 최솟값을 만드는 i를 지정하고 r을 구해보자.
1<=i<j<n 이므로
[1,i]에서 -s(2,i)+s(1,i)의 최솟값은 증가하는 j마다 한 번씩 구하여 최솟값을 갱신하며 저장하고 있으면 바로 쓸 수 있다.

구간을 지정하는 순서를 바꿔 최종적인 답을 구하자.

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
int n, r = 1e9;
vector<int> v[3];
int main() {
    scanf("%d", &n);
    for (int i = 0; i<3; i++)
        for (int j = 0, x; j<n; j++) scanf("%d", &x), v[i].push_back(x);
    sort(v, v + 3);
    do {
        int s = 0, s0 = v[0][0], s1 = v[1][0], s2 = 0, mini = 1e9;
        for (int i = 0; i<n; i++) s += v[0][i];
        for (int i = 1; i<n - 1; i++) {
            s2 += v[2][i - 1];
            mini = min(mini, s2 - s1);
            s0 += v[0][i];
            s1 += v[1][i];
            r = min(r, s - s0 + s1 + mini);
        }
    } while (next_permutation(v, v + 3));
    printf("%d", r);
    return 0;
}