1555-C, *1300

Problem - 1555C - Codeforces

문제

• $2 \times m\ \mathrm{matrix}$ 위에 동전이 깔려있다
• Alice, Bob 두 사람이 게임은 한다.
• 두 사람은 오른쪽이나 아래로 밖에 못 가며 이동한 칸에 있는 동전은 주워간다
• Alice가 먼저 $1\times 1$부터 $2\times m$까지 이동한다
• 그 후 Bob이 $1\times 1$부터 $2\times m$까지 이동한다
• $score$는 $\mathrm{Bob}$이 주운 돈의 합
• Alice는 $score$를 최소화하도록 이동하고 Bob은 최대화하도록 움직인다
• $score$?

 

$O(m)$

Alice가 아래로 이동하는 열을 down 이라고 하자
그러면 Bob의 이동경로는 다음 두 가지 중 하나이다
i) ㄱ
ii) ㄴ

#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
 
int m;
int top[100001] {};
int bottom[100001] {};
 
void make_accomulate()
{
    for(int i = m-2; i > 0; i--) top[i] += top[i+1];
    for(int i = 1; i < m-1; i++) bottom[i] += bottom[i-1];
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int t;
    cin >> t;
    while(t--){
        cin >> m;
        for(int i = 0; i < m; i++) cin >> top[i];
        for(int i = 0; i < m; i++) cin >> bottom[i];
 
        if(m >= 2) make_accomulate();
 
        int score = 1000010001;
        score = min(score, top[1]);
        for(int down = 1; down < m-1; down++) score = min(score, max(top[down+1], bottom[down-1]));
        score = min(score, bottom[m-2]);
 
        cout << score << endl;
    }
 
 
 
 
    return 0;
}cs