Submission #1056835

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056835		j_vdd16	Sightseeing in Kyoto (JOI22_kyoto)	C++17	0 / 100	1 ms	604 KiB

kyoto

#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] * (bestJ2 - j1) + b[bestJ] * (bestI2 - i1) < a[bestI] * (bestJ2 - j1) + b[bestJ2] * (bestI2 - 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] * (bestJ2 - j1) + b[bestJ] * (bestI2 - i1) < a[bestI] * (bestJ2 - j1) + b[bestJ2] * (bestI2 - 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;

    /*
11 11
1 2 3 4 5 6 7 8 9 10 11
1 2 3 4 5 6 7 8 9 10 11
    */

    cout << solve(0, 0, h - 1, w - 1) << endl;
    cerr << memoize.size() << endl;

	return 0;
}

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