oj.uz

Submission #89875

# Submission time Handle Problem Language Result Execution time Memory
89875 2018-12-18T17:44:48 Z vex Cover (COCI18_cover) C++14
48 / 120
 14 ms 852 KB 
#include <bits/stdc++.h>
#define maxn 5005
#define pii pair<int,int>
#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
48.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Incorrect 2 ms 460 KB Output isn't correct
6 Incorrect 2 ms 460 KB Output isn't correct
7 Incorrect 2 ms 616 KB Output isn't correct
8 Incorrect 3 ms 616 KB Output isn't correct
9 Incorrect 8 ms 752 KB Output isn't correct
10 Incorrect 14 ms 852 KB Output isn't correct