Submission #311923

#TimeUsernameProblemLanguageResultExecution timeMemory
311923colazcyCover (COCI18_cover)C++17
0 / 120
47 ms65540 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...