oj.uz

Submission #593035

# Submission time Handle Problem Language Result Execution time Memory
593035 2022-07-10T08:56:20 Z jhnah917 Sightseeing in Kyoto (JOI22_kyoto) C++14
0 / 100
 13 ms 32264 KB 
#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]);
    SA[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]);
    SB[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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 32212 KB Output is correct
2 Incorrect 13 ms 32212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 32264 KB Output is correct
2 Incorrect 12 ms 32184 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 32212 KB Output is correct
2 Incorrect 13 ms 32212 KB Output isn't correct
3 Halted 0 ms 0 KB -