Submission #311925

#	Time	Username	Problem	Language	Result	Execution time	Memory
311925		colazcy	Cover (COCI18_cover)	C++17	0 / 120	5 ms	512 KiB

cover

#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
const int maxn = 5e3 + 100;
typedef long long ll;
inline int read(){
	int x = 0,f = 1;char c = getchar();
	while(!isdigit(c))f = c == '-' ? -1 : f,c = getchar();
	while(isdigit(c))x = x * 10 + c - '0',c = getchar();
	return x;
}
struct point{
	int x,y;
	bool operator < (const point &rhs)const{
		if(x != rhs.x)return x < rhs.x;
		return y < rhs.y;
	}	
}tmp[maxn],p[maxn];
ll f[2][maxn],ans = 0x7fffffffffffffff;
inline void chk(ll &x,ll y){x = min(x,y);}
int n,tot;
int main(){
//	freopen("cover.in","r",stdin);
//	freopen("cover.out","w",stdout);
	n = read();
	for(int i = 1;i <= n;i++)
		tmp[i].x = abs(read()),tmp[i].y = abs(read());
	sort(tmp + 1,tmp + 1 + n);
	for(int i = 1;i <= n;i++){
		while(tot && p[tot].y <= tmp[i].y)tot--;
		p[++tot] = tmp[i];
	}
	for(int i = 0;i < 2;i++)
		for(int j = 0;j < 2;j++)
			f[i][j] = 0x3f3f3f3f3f3f3f3f;
	f[1][1] = 1ll * p[1].x * p[1].y;
	for(int i = 1;i < tot;i++){
		int opt = i & 1;
		for(int j = 1;j <= i;j++){
			chk(f[opt ^ 1][j],f[opt][j] + 1ll * (p[i + 1].x - p[i].x) * p[j].y);
			chk(f[opt ^ 1][i + 1],f[opt][j] + 1ll * p[i + 1].x * p[i + 1].y);
		}
	}
	for(int i = 1;i <= tot;i++)chk(ans,f[tot & 1][i]);
	printf("%lld\n",ans * 4);
	fclose(stdin);
	fclose(stdout);
	return 0; 
}

• Subtask 1: 0 / 120