oj.uz

Submission #1056076

# Submission time Handle Problem Language Result Execution time Memory
1056076 2024-08-13T07:38:57 Z j_vdd16 Sightseeing in Kyoto (JOI22_kyoto) C++17
10 / 100
 2000 ms 225188 KB 
#include <algorithm>
#include <bitset>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

#define int long long
#define loop(X, N) for(int X = 0; X < (N); X++)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;

typedef uint64_t u64;
typedef int64_t i64;

int h, w;
vi a, b;

struct SegTree {
    int n, N;
    vi tree;
    vi values;

    SegTree() = default;
    SegTree(const vi& _values) {
        values = _values;
        n = values.size();
        N = 1;
        while (N < n) N *= 2;

        tree = vi(2 * N);
        loop(i, n) tree[N + i] = i;

        for (int i = N - 1; i >= 1; i--)
            tree[i] = merge(tree[2 * i], tree[2 * i + 1]);
    }

    int merge(int x, int y) {
        return values[x] < values[y] ? x : y;
    }

    int get(int l, int r, int i = 1, int tl = 0, int tr = -1) {
        if (tr == -1) tr = N;

        if (r <= tl || l >= tr) return l; //identity
        if (l <= tl && r >= tr) return tree[i];

        int tm = (tl + tr) / 2;
        int res = merge(get(l, r, 2 * i, tl, tm), get(l, r, 2 * i + 1, tm, tr));
        return res;
    }
};

SegTree minA, minB;

int minIdx(const vi& arr, int l, int r) {
    int best = l;
    for (int i = l; i <= r; i++) {
        if (arr[i] < arr[best])
            best = i;
    }

    return best;
}
int minIdxA(int l, int r) {
    return minA.get(l, r + 1);
}
int minIdxB(int l, int r) {
    return minB.get(l, r + 1);
}
int maxIdx(const vi& arr, int l, int r) {
    int best = l;
    for (int i = l; i <= r; i++) {
        if (arr[i] > arr[best])
            best = i;
    }

    return best;
}

map<pair<ii, ii>, int> memoize;
int solve(int i1, int j1, int i2, int j2) {
    if (i1 == i2) {
        return (j2 - j1) * a[i1];
    }
    if (j1 == j2) {
        return (i2 - i1) * b[j1];
    }

    if (memoize.count({{i1, j1}, {i2, j2}}))
        return memoize[{{i1, j1}, {i2, j2}}];

    int bestI = minIdxA(i1, i2);
    int bestJ = minIdxB(j1, j2);

    int res;
    if (bestI == i1 && bestJ == j1) {
        int bestI2 = minIdxA(i1 + 1, i2);
        int bestJ2 = minIdxB(j1 + 1, j2);

        // if (a[bestI2] * (j2 - j1) + b[bestJ] * (i2 - i1) < a[bestI] * (j2 - j1) + b[bestJ2] * (i2 - i1))
        //     return solve(i1, j1, bestI2, bestJ) + solve(bestI2, bestJ, i2, j2);
        // else
        //     return solve(i1, j1, bestI, bestJ2) + solve(bestI, bestJ2, i2, j2);

        res = min(solve(i1, j1, bestI2, bestJ) + solve(bestI2, bestJ, i2, j2), solve(i1, j1, bestI, bestJ2) + solve(bestI, bestJ2, i2, j2));
    }
    else if (bestI == i2 && bestJ == j2) {
        int bestI2 = minIdxA(i1, i2 - 1);
        int bestJ2 = minIdxB(j1, j2 - 1);

        // if (a[bestI2] * (j2 - j1) + b[bestJ] * (i2 - i1) < a[bestI] * (j2 - j1) + b[bestJ2] * (i2 - i1))
        //     return solve(i1, j1, bestI2, bestJ) + solve(bestI2, bestJ, i2, j2);
        // else
        //     return solve(i1, j1, bestI, bestJ2) + solve(bestI, bestJ2, i2, j2);

        res = min(solve(i1, j1, bestI2, bestJ) + solve(bestI2, bestJ, i2, j2), solve(i1, j1, bestI, bestJ2) + solve(bestI, bestJ2, i2, j2));
    }
    else {
        res = solve(i1, j1, bestI, bestJ) + solve(bestI, bestJ, i2, j2);
    }

    memoize[{{i1, j1}, {i2, j2}}] = res;
    return res;
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

    cin >> h >> w;

    a = vi(h);
    b = vi(w);
    loop(i, h) cin >> a[i];
    loop(i, w) cin >> b[i];

    minA = SegTree(a);
    minB = SegTree(b);

    // vvi scores(h, vi(w));
    // loop(i, h) {
    //     scores[i][0] = i * b[0];
    // }
    // loop(i, w) {
    //     scores[0][i] = i * a[0];
    // }

    // for (int i = 1; i < h; i++) {
    //     for (int j = 1; j < w; j++) {
    //         scores[i][j] = min(scores[i - 1][j] + b[j], scores[i][j - 1] + a[i]);
    //     }
    // }
    //cout << scores[h - 1][w - 1] << endl;

    cout << solve(0, 0, h - 1, w - 1);

	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 177 ms 28184 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 248 ms 35768 KB Output is correct
17 Correct 640 ms 78944 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 117 ms 18044 KB Output is correct
4 Correct 19 ms 6492 KB Output is correct
5 Execution timed out 2108 ms 225188 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 177 ms 28184 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 248 ms 35768 KB Output is correct
17 Correct 640 ms 78944 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 0 ms 344 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 117 ms 18044 KB Output is correct
32 Correct 19 ms 6492 KB Output is correct
33 Execution timed out 2108 ms 225188 KB Time limit exceeded
34 Halted 0 ms 0 KB -