Submission #311927

# Submission time Handle Problem Language Result Execution time Memory
311927 2020-10-12T03:19:21 Z colazcy Cover (COCI18_cover) C++17
0 / 120
6 ms 384 KB
#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 * f;
}
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; 
}
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 256 KB Output isn't correct
2 Incorrect 0 ms 256 KB Output isn't correct
3 Incorrect 0 ms 256 KB Output isn't correct
4 Incorrect 0 ms 256 KB Output isn't correct
5 Incorrect 0 ms 256 KB Output isn't correct
6 Incorrect 0 ms 256 KB Output isn't correct
7 Incorrect 1 ms 384 KB Output isn't correct
8 Incorrect 1 ms 384 KB Output isn't correct
9 Incorrect 4 ms 384 KB Output isn't correct
10 Incorrect 6 ms 360 KB Output isn't correct