제출 #1272264

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1272264		thuhienne	Cover (COCI18_cover)	C++20	120 / 120	18 ms	600 KiB

cover

#include <bits/stdc++.h>
using namespace std;

int n;
pair <int,int> points[5009];

int maxheight[5009];

vector <int> X,Y;

long long dp[5009];

int main() {
	ios_base::sync_with_stdio(0);cin.tie(nullptr);
	//freopen(".inp","r",stdin);
	//freopen(".out","w",stdout);
	cin >> n;
	for (int i = 1;i <= n;i++) {
		cin >> points[i].first >> points[i].second;
		points[i].first = abs(points[i].first);
		points[i].second = abs(points[i].second);
		X.push_back(points[i].first);
		Y.push_back(points[i].second);
	}
	
	sort(X.begin(),X.end());
	sort(Y.begin(),Y.end());
	X.resize(unique(X.begin(),X.end()) - X.begin());
	Y.resize(unique(Y.begin(),Y.end()) - Y.begin());
	
	for (int i = 1;i <= n;i++) {
		points[i].first = lower_bound(X.begin(),X.end(),points[i].first) - X.begin();
		points[i].second = lower_bound(Y.begin(),Y.end(),points[i].second) - Y.begin();
		maxheight[points[i].first] = max(maxheight[points[i].first],points[i].second);
	}
	
	int n = X.size(),m = Y.size();
	
	for (int i = 0;i < n;i++) {
		long long mindp = 1e18;
		for (int j = m - 1;j >= 0;j--) {
			if (j < maxheight[i]) {
				dp[j] = 1e18;
				continue;
			}
			long long oldval = dp[j];
			dp[j] = 1e18;
			//TH1: Keo dai ra
			dp[j] = min(dp[j],oldval + 1ll * Y[j] * (X[i] - (i == 0 ? 0 : X[i - 1]) ) );
			//TH2: Tao luon hcn moi
			dp[j] = min(dp[j],mindp + 1ll * Y[j] * X[i]);
			
			mindp = min(mindp,oldval);
		}
	}
	cout << *min_element(dp,dp + m) * 4;
	
}

/*
  Nho doi vai em gay
			  co gai ay ngoi duoi goc pho nen tho ...
*/

• Subtask 1: 120 / 120