Submission #105386

#	Time	Username	Problem	Language	Result	Execution time	Memory
105386		BartolM	Cover (COCI18_cover)	C++17	120 / 120	6 ms	512 KiB

cover

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;

const ll INF=0x3f3f3f3f;
const int N=5005;

int n;
pll p[N];
vector <pll> v;
ll dp[N];

void load() {
    scanf("%d", &n);
    for (int i=1; i<=n; ++i) {
        scanf("%lld %lld", &p[i].X, &p[i].Y);
        p[i].X=abs(p[i].X);
        p[i].Y=abs(p[i].Y);
    }
}

void solve() {
    sort(p+1, p+n+1);
    ll ma=0;
    for (int i=n; i>=1; --i) {
        if (p[i].Y>ma) {
            ma=p[i].Y;
            v.pb(p[i]);
        }
    }
    n=v.size();
    v.pb(mp(0, INF));
    reverse(v.begin(), v.end());
//    for (int i=0; i<v.size(); ++i) {
//        printf("%lld %lld\n", v[i].X, v[i].Y);
//    }
    for (int i=1; i<=n; ++i) {
        dp[i]=INF*INF;
        for (int j=0; j<i; ++j) {
            dp[i]=min(dp[i], dp[j]+v[j+1].Y*v[i].X);
        }
    }
    printf("%lld\n", dp[n]*4);
}

int main() {
    load();
    solve();
    return 0;
}

Compilation message (stderr)

cover.cpp: In function 'void load()':
cover.cpp:28:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
cover.cpp:30:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %lld", &p[i].X, &p[i].Y);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 120 / 120