Submission #750260

#	Time	Username	Problem	Language	Result	Execution time	Memory
750260		bgnbvnbv	Cover (COCI18_cover)	C++14	120 / 120	15 ms	468 KiB

cover

#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<ll,ll>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=2e5;
const ll inf=1e18;
const ll mod=1e9+7;
ll n;
ll dp[maxN];
struct qq
{
    ll a,b;
    bool operator<(const qq&o)
    {
        return a*b<o.a*o.b;
    }
}x[maxN];
vector<pli>vec;
void solve()
{
    cin >> n;
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        cin >> x[i].a >> x[i].b;
        x[i].a=abs(x[i].a);
        x[i].b=abs(x[i].b);
        ans+=x[i].a*x[i].b;
    }
    sort(x+1,x+n+1);
    for(int i=1;i<=n;i++)
    {
        bool ok=true;
        for(int j=i+1;j<=n;j++)
        {
            if(x[i].a<=x[j].a&&x[i].b<=x[j].b)
            {
                ok=false;
                break;
            }
        }
        if(ok)vec.pb({x[i].a,x[i].b});

    }
    sort(vec.begin(),vec.end());
    dp[0]=0;
    for(int i=0;i<vec.size();i++)
    {
        dp[i+1]=inf;
        for(int j=-1;j<i;j++)
        {
            dp[i+1]=min(dp[i+1],dp[j+1]+vec[j+1].se*vec[i].fi);
        }
    }
    cout <<dp[vec.size()]*4;
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Compilation message (stderr)

cover.cpp: In function 'void solve()':
cover.cpp:52:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for(int i=0;i<vec.size();i++)
      |                 ~^~~~~~~~~~~

• Subtask 1: 120 / 120