Submission #609637

#	Time	Username	Problem	Language	Result	Execution time	Memory
609637		Tigryonochekk	Sightseeing in Kyoto (JOI22_kyoto)	C++17	40 / 100	72 ms	33256 KiB

kyoto

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <string>
using namespace std;
#define ll long long
#define pii pair<int, int>
const int A = 1002, N = 1e5 + 2;
const ll inf = 1e18 + 49;

int h, w;
int a[N], b[N];

int fto[A], lto[A];
int fsu[A], lsu[A];
vector<int> toxs, syuns;

ll dp[2 * A][2 * A];

int main() {
	cin >> h >> w;
	for (int i = 1; i <= h; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= w; i++) {
		cin >> b[i];
	}
	if (h <= 1000 && w <= 1000) {
		for (int i = 1; i <= h; i++) {
			for (int j = 1; j <= w; j++) {
				dp[i][j] = inf;
				dp[1][1] = 0;
				if (i > 1)
					dp[i][j] = min(dp[i][j], dp[i - 1][j] + b[j]);
				if (j > 1)
					dp[i][j] = min(dp[i][j], dp[i][j - 1] + a[i]);
			}
		}
		cout << dp[h][w] << endl;
	}
	else {
		for (int i = 1; i <= h; i++) {
			if (!fto[a[i]]) 
				fto[a[i]] = i;
		}
		for (int i = 1; i <= w; i++) {
			if (!fsu[b[i]]) 
				fsu[b[i]] = i;
		}
		for (int i = h; i >= 1; i--) {
			if (!lto[a[i]]) 
				lto[a[i]] = i;
		}
		for (int i = w; i >= 1; i--) {
			if (!lsu[b[i]]) 
				lsu[b[i]] = i;
		}
		for (int i = 1; i <= h; i++) {
			if (fto[a[i]] == i)
				toxs.push_back(i);
			else if (lto[a[i]] == i)
				toxs.push_back(i);

		}
		for (int i = 1; i <= w; i++) {
			if (fsu[b[i]] == i)
				syuns.push_back(i);
			else if (lsu[b[i]] == i)
				syuns.push_back(i);

		}

		int n = toxs.size(), m = syuns.size();
		dp[0][0] = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				dp[i][j] = inf;
				dp[0][0] = 0;
				if (i) {
					dp[i][j] = min(dp[i][j], dp[i - 1][j] + b[syuns[j]] * (toxs[i] - toxs[i - 1]));
				}
				if (j) {
					dp[i][j] = min(dp[i][j], dp[i][j - 1] + a[toxs[i]] * (syuns[j] - syuns[j - 1]));
				}
			}
		}
		cout << dp[n - 1][m - 1] << endl;
	}
	return 0;
}

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