oj.uz

Submission #994244

# Submission time Handle Problem Language Result Execution time Memory
994244 2024-06-07T09:45:05 Z vjudge1 Sightseeing in Kyoto (JOI22_kyoto) C++17
0 / 100
 16 ms 74012 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MAXN = 100'001;
const int MAXM = 3001;

ll dp[MAXM][MAXM], a[MAXN], b[MAXN], idxa[MAXN], idxb[MAXN], timera = 1, timerb = 1;
set<ll> hva, hvb;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= m; i++) cin >> b[i];
    for (int i = 0; i < MAXM; i++) {
        for (int j = 0; j < MAXM; j++) {
            dp[i][j] = 1e18;
        }
    }
    for (int i = 1; i <= n; i++) {
        if (!hva.count(a[i]) || i == n) {
            hva.insert(a[i]);
            idxa[timera++] = i;
        }
    }
    for (int i = 1; i <= m; i++) {
        if (!hvb.count(b[i]) || i == m) {
            hvb.insert(b[i]);
            idxb[timerb++] = i;
        }
    }
    dp[1][1] = 0;
    for (int i = 1; i < timera; i++) {
        for (int j = 1; j < timerb; j++) {
            dp[i][j+1] = min(dp[i][j+1], dp[i][j] + a[i] * (idxb[j+1] - idxb[j]));
            dp[i+1][j] = min(dp[i+1][j], dp[i][j] + b[j] * (idxa[i+1] - idxa[i]));
        }
    }
    cout << dp[timera-1][timerb-1] << "\n";
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 73820 KB Output is correct
2 Correct 10 ms 73820 KB Output is correct
3 Correct 11 ms 73820 KB Output is correct
4 Correct 11 ms 73752 KB Output is correct
5 Correct 11 ms 73756 KB Output is correct
6 Correct 11 ms 73816 KB Output is correct
7 Correct 11 ms 73820 KB Output is correct
8 Correct 11 ms 73820 KB Output is correct
9 Correct 15 ms 73820 KB Output is correct
10 Correct 14 ms 73820 KB Output is correct
11 Correct 14 ms 73820 KB Output is correct
12 Correct 16 ms 74012 KB Output is correct
13 Correct 14 ms 73820 KB Output is correct
14 Correct 15 ms 73820 KB Output is correct
15 Correct 14 ms 73952 KB Output is correct
16 Correct 15 ms 73820 KB Output is correct
17 Correct 11 ms 73820 KB Output is correct
18 Correct 10 ms 73820 KB Output is correct
19 Correct 10 ms 73820 KB Output is correct
20 Correct 10 ms 73728 KB Output is correct
21 Correct 10 ms 73820 KB Output is correct
22 Correct 11 ms 73812 KB Output is correct
23 Correct 11 ms 73816 KB Output is correct
24 Correct 11 ms 73804 KB Output is correct
25 Correct 10 ms 73820 KB Output is correct
26 Correct 11 ms 73760 KB Output is correct
27 Incorrect 10 ms 73820 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

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

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 73820 KB Output is correct
2 Correct 10 ms 73820 KB Output is correct
3 Correct 11 ms 73820 KB Output is correct
4 Correct 11 ms 73752 KB Output is correct
5 Correct 11 ms 73756 KB Output is correct
6 Correct 11 ms 73816 KB Output is correct
7 Correct 11 ms 73820 KB Output is correct
8 Correct 11 ms 73820 KB Output is correct
9 Correct 15 ms 73820 KB Output is correct
10 Correct 14 ms 73820 KB Output is correct
11 Correct 14 ms 73820 KB Output is correct
12 Correct 16 ms 74012 KB Output is correct
13 Correct 14 ms 73820 KB Output is correct
14 Correct 15 ms 73820 KB Output is correct
15 Correct 14 ms 73952 KB Output is correct
16 Correct 15 ms 73820 KB Output is correct
17 Correct 11 ms 73820 KB Output is correct
18 Correct 10 ms 73820 KB Output is correct
19 Correct 10 ms 73820 KB Output is correct
20 Correct 10 ms 73728 KB Output is correct
21 Correct 10 ms 73820 KB Output is correct
22 Correct 11 ms 73812 KB Output is correct
23 Correct 11 ms 73816 KB Output is correct
24 Correct 11 ms 73804 KB Output is correct
25 Correct 10 ms 73820 KB Output is correct
26 Correct 11 ms 73760 KB Output is correct
27 Incorrect 10 ms 73820 KB Output isn't correct
28 Halted 0 ms 0 KB -