Submission #311923

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
311923	2020-10-12T03:17:18 Z	colazcy	Cover (COCI18_cover)	C++17	0 / 120	47 ms	65540 KB

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[maxn][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 < maxn;i++)
		for(int j = 0;j < maxn;j++)
			f[i][j] = 0x3f3f3f3f3f3f3f3f;
	f[1][1] = 1ll * p[1].x * p[1].y;
	for(int i = 1;i < tot;i++)	
		for(int j = 1;j <= i;j++){
			chk(f[i + 1][j],f[i][j] + 1ll * (p[i + 1].x - p[i].x) * p[j].y);
			chk(f[i + 1][i + 1],f[i][j] + 1ll * p[i + 1].x * p[i + 1].y);
		}
	for(int i = 1;i <= tot;i++)chk(ans,f[tot][i]);
	printf("%lld\n",ans * 4);
	fclose(stdin);
	fclose(stdout);
	return 0; 
}

Subtask #1

0 / 120.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	47 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
2	Runtime error	41 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
3	Runtime error	40 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
4	Runtime error	41 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
5	Runtime error	41 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
6	Runtime error	42 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
7	Runtime error	42 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
8	Runtime error	38 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
9	Runtime error	39 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
10	Runtime error	42 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)