Submission #887653

#	Time	Username	Problem	Language	Result	Execution time	Memory
887653		TAhmed33	Sightseeing in Kyoto (JOI22_kyoto)	C++98	40 / 100	1245 ms	158512 KiB

kyoto

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 25;
typedef long long ll;
ll n, m, a[MAXN], b[MAXN];
ll mnp[MAXN][2], mns[MAXN][2];
vector <ll> remx = {0}, remy = {0};
ll dp[3001][3001];
int main () {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		mnp[i][0] = mns[i][0] = a[i];
	}
	for (int i = 1; i <= m; i++) {
		cin >> b[i];
		mnp[i][1] = mns[i][1] = b[i];
	}
	for (int i = 2; i <= n; i++) {
		mnp[i][0] = min(mnp[i][0], mnp[i - 1][0]);
	}
	for (int i = 2; i <= m; i++) {
		mnp[i][1] = min(mnp[i][1], mnp[i - 1][1]);
	}
	for (int i = n - 1; i >= 1; i--) {
		mns[i][0] = min(mns[i][0], mns[i + 1][0]);
	}
	for (int i = m - 1; i >= 1; i--) {
		mns[i][1] = min(mns[i][1], mns[i + 1][1]);
	}
	for (int i = 1; i <= n; i++) {
		bool flag = i > 1 && a[i] >= mnp[i - 1][0];
		flag &= i < n && a[i] >= mns[i + 1][0];
		if (flag) continue;
		remx.push_back(i);
	}
	for (int i = 1; i <= m; i++) {
		bool flag = i > 1 && b[i] >= mnp[i - 1][1];
		flag &= i < m && b[i] >= mns[i + 1][1];
		if (flag) continue;
		remy.push_back(i);
	}
	for (int i = 1; i < (int)remx.size(); i++) {
		for (int j = 1; j < (int)remy.size(); j++) {
			if (i == j && j == 1) continue;
			dp[i][j] = 1e18;
			if (i > 1) dp[i][j] = min(dp[i][j], dp[i - 1][j] + b[remy[j]] * (remx[i] - remx[i - 1]));
			if (j > 1) dp[i][j] = min(dp[i][j], dp[i][j - 1] + a[remx[i]] * (remy[j] - remy[j - 1]));
		}
	}
	cout << dp[(int)remx.size() - 1][(int)remy.size() - 1] << '\n';
}

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