제출 #593033

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
593033		jhnah917	Sightseeing in Kyoto (JOI22_kyoto)	C++14	10 / 100	112 ms	74164 KiB

kyoto

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll N, M, A[101010], B[101010], D[2020][2020];
ll PA[101010], SA[101010], PB[101010], SB[101010];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M;
    for(int i=1; i<=N; i++) cin >> A[i];
    for(int i=1; i<=M; i++) cin >> B[i];
    PA[1] = A[1]; for(int i=2; i<=N; i++) PA[i] = min(PA[i-1], A[i]);
    PA[N] = A[N]; for(int i=N-1; i>=1; i--) SA[i] = min(SA[i+1], A[i]);
    PB[1] = B[1]; for(int i=2; i<=M; i++) PB[i] = min(PB[i-1], B[i]);
    PB[M] = B[M]; for(int i=M-1; i>=1; i--) SB[i] = min(SB[i+1], B[i]);

    vector<pair<ll, ll>> U, V;
    for(int i=1; i<=N; i++) if(!(PA[i-1] >= A[i] && A[i] <= SA[i+1])) U.emplace_back(A[i], i);
    for(int i=1; i<=M; i++) if(!(PB[i-1] >= B[i] && B[i] <= SB[i+1])) V.emplace_back(B[i], i);
    N = U.size(); M = V.size();

    memset(D, 0x3f, sizeof D); D[0][0] = 0;
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            if(i + j == 0) continue;
            if(i > 0) D[i][j] = min(D[i][j], D[i-1][j] + V[j].first * (U[i].second - U[i-1].second));
            if(j > 0) D[i][j] = min(D[i][j], D[i][j-1] + U[i].first * (V[j].second - V[j-1].second));
        }
    }
    cout << D[N-1][M-1];
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 30
• Subtask 3: 0 / 60