Submission #733641

#	Time	Username	Problem	Language	Result	Execution time	Memory
733641		QwertyPi	Sightseeing in Kyoto (JOI22_kyoto)	C++14	40 / 100	104 ms	31800 KiB

kyoto

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define INF (1LL << 60)
using namespace std;

int chmin(int& x, int y) {
	return x = min(x, y);
}

vector<pair<int, int>> s_inc(const vector<pair<int, int>>& v){
	vector<pair<int, int>> res;
	for(auto i : v){
		while(res.size() && i.fi <= res.back().fi) res.pop_back();
		res.push_back(i);
	}
	return res;
}

int dp[1001][1001];
int solve(vector<pair<int, int>> a, vector<pair<int, int>> b){
	a = s_inc(a), b = s_inc(b);
	int n = a.size(), m = b.size();
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			dp[i][j] = INF;
		}
	}
	dp[0][0] = 0;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			if(i > 0) chmin(dp[i][j], dp[i - 1][j] + b[j].fi * (a[i].se - a[i - 1].se));
			if(j > 0) chmin(dp[i][j], dp[i][j - 1] + a[i].fi * (b[j].se - b[j - 1].se));
		}
	}
	return dp[n - 1][m - 1];
}

int32_t main(){
	int n, m; cin >> n >> m;
	vector<int> a, b;
	for(int i = 0; i < n; i++){
		int v; cin >> v; a.push_back(v);
	}
	for(int i = 0; i < m; i++){
		int v; cin >> v; b.push_back(v);
	}
	int min_a = 0, min_b = 0;
	for(int i = 1; i < n; i++){
		if(a[i] < a[min_a]) min_a = i;
	}
	for(int i = 1; i < m; i++){
		if(b[i] < b[min_b]) min_b = i;
	}
	
	vector<pair<int, int>> a1, a2, b1, b2;
	
	for(int i = min_a; i >= 0; i--) a1.push_back({a[i] - a[min_a], min_a - i});
	for(int i = min_a; i < n; i++) a2.push_back({a[i] - a[min_a], i - min_a});
	for(int i = min_b; i >= 0; i--) b1.push_back({b[i] - b[min_b], min_b - i});
	for(int i = min_b; i < m; i++) b2.push_back({b[i] - b[min_b], i - min_b});
	int ans = (n - 1) * b[min_b] + (m - 1) * a[min_a] + solve(a1, b1) + solve(a2, b2);
	cout << ans << endl;
}

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