Submission #89877

#	Time	Username	Problem	Language	Result	Execution time	Memory
89877		vex	Cover (COCI18_cover)	C++14	120 / 120	16 ms	812 KiB

cover

#include <bits/stdc++.h>
#define maxn 5005
#define pii pair<long long,long long>
#define x first
#define y second
using namespace std;

int n;
pii a[maxn];
pii sol[maxn];

bool veci(pii p1,pii p2)
{
    return p1.x>=p2.x && p1.y>=p2.y;
}

long long dp[maxn];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i].x>>a[i].y;
        if(a[i].x<0)a[i].x=-a[i].x;
        if(a[i].y<0)a[i].y=-a[i].y;
    }

    sort(a,a+n);
    int len=0;

    for(int i=0;i<n;i++)
    {
        bool bit=true;
        for(int j=i+1;j<n;j++)
        {
            if(veci(a[j],a[i]))bit=false;
        }
        if(bit)
        {
            len++;
            sol[len]=a[i];
        }
    }

    //for(int i=1;i<=len;i++)cout<<sol[i].x<<","<<sol[i].y<<" ";cout<<endl;

    dp[0]=0LL;
    for(int i=1;i<=len;i++)
    {
        dp[i]=dp[i-1]+4*sol[i].x*sol[i].y;
        for(int j=1;j<i;j++)
        {
            long long tre=dp[j-1]+4*sol[i].x*sol[j].y;
            if(tre<dp[i])dp[i]=tre;
        }
    }

    //for(int i=0;i<=len;i++)cout<<dp[i]<<" ";cout<<endl;

    cout<<dp[len]<<endl;
    return 0;
}

• Subtask 1: 120 / 120