oj.uz

Submission #105386

# Submission time Handle Problem Language Result Execution time Memory
105386 2019-04-11T17:42:33 Z BartolM Cover (COCI18_cover) C++17
120 / 120
 6 ms 512 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 4 ms 512 KB Output is correct
10 Correct 6 ms 512 KB Output is correct