Submission #105387

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
105387	2019-04-11T18:04:18 Z	BartolM	Cover (COCI18_cover)	C++17	120 / 120	3 ms	512 KB

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;
vector <pll> hull;
ll dp[N];

int ccw(pll a, pll b, pll c) {
    ll cc=a.X*(b.Y-c.Y)+b.X*(c.Y-a.Y)+c.X*(a.Y-b.Y);
    if (cc>0) return 1;
    else if (cc==0) return 0;
    else return -1;
}

void dodaj(pll pp) {
    while (hull.size()>1 && ccw(hull[(int)hull.size()-2], hull.back(), pp)>=0) hull.pop_back();
    hull.pb(pp);
}

ll nadji(ll x) {
    int lo=0, hi=hull.size()-1, mid1, mid2;
    while (lo<hi) {
        mid1=(lo+hi)/2;
        mid2=mid1+1;
        ll val1=hull[mid1].X*x+hull[mid1].Y;
        ll val2=hull[mid2].X*x+hull[mid2].Y;
        if (val1<val2) hi=mid1;
        else if (val2<val1) lo=mid2;
        else return val1;
    }
    return hull[lo].X*x+hull[lo].Y;
}

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);
//    }
    dodaj(mp(v[1].Y, 0ll));
    for (int i=1; i<=n; ++i) {
        dp[i]=nadji(v[i].X);
        if (i!=n) dodaj(mp(v[i+1].Y, dp[i]));
    }
    printf("%lld\n", dp[n]*4);
}

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

Compilation message

cover.cpp: In function 'void load()':
cover.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
cover.cpp:57: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	3 ms	384 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	128 KB	Output is correct
5	Correct	2 ms	384 KB	Output is correct
6	Correct	2 ms	384 KB	Output is correct
7	Correct	2 ms	384 KB	Output is correct
8	Correct	3 ms	384 KB	Output is correct
9	Correct	3 ms	384 KB	Output is correct
10	Correct	3 ms	512 KB	Output is correct