oj.uz

Submission #89877

# Submission time Handle Problem Language Result Execution time Memory
89877 2018-12-18T17:49:50 Z vex Cover (COCI18_cover) C++14
120 / 120
 16 ms 812 KB 
#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.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 392 KB Output is correct
4 Correct 4 ms 436 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 2 ms 532 KB Output is correct
7 Correct 2 ms 532 KB Output is correct
8 Correct 3 ms 588 KB Output is correct
9 Correct 7 ms 792 KB Output is correct
10 Correct 16 ms 812 KB Output is correct