제출 #593039

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
593039		jhnah917	Sightseeing in Kyoto (JOI22_kyoto)	C++14	40 / 100	841 ms	83156 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[0] = PB[0] = SA[N+1] = SB[M+1] = 0x3f3f3f3f3f3f3f3f;
    for(int i=1; i<=N; i++) PA[i] = min(PA[i-1], A[i]);
    for(int i=N; i>=1; i--) SA[i] = min(SA[i+1], A[i]);
    for(int i=1; i<=M; i++) PB[i] = min(PB[i-1], B[i]);
    for(int i=M; 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(A[i] < PA[i-1] || A[i] < SA[i+1]) U.emplace_back(A[i], i);
    for(int i=1; i<=M; i++) if(B[i] < PB[i-1] || 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: 30 / 30
• Subtask 3: 0 / 60