oj.uz

답안 #311923

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
311923 2020-10-12T03:17:18 Z colazcy Cover (COCI18_cover) C++17
0 / 120
 47 ms 65540 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;
}
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

# 결과 실행 시간 메모리 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)