oj.uz

Submission #750260

# Submission time Handle Problem Language Result Execution time Memory
750260 2023-05-29T08:43:05 Z bgnbvnbv Cover (COCI18_cover) C++14
120 / 120
 15 ms 468 KB 
#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

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.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 ms 344 KB Output is correct
9 Correct 9 ms 468 KB Output is correct
10 Correct 15 ms 468 KB Output is correct