Submission #105114

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
105114	2019-04-10T15:00:54 Z	fbosnjak	Cover (COCI18_cover)	C++14	120 / 120	93 ms	760 KB

cover

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int maxn = 5050;
const ll maxv = 1e12;

int N;
ll a, b;
vector <pair <ll, ll> > v, v1;
ll dp[maxn];
vector <pair <ll, ll> > convex;

int ccw(pair <ll, ll> x, pair <ll, ll> y, pair <ll, ll> z)
{
    ll val = x.first * (y.second - z.second) +
             y.first * (z.second - x.second) +
             z.first * (x.second - y.second);

    if (val > 0) return 1;
    if (val == 0) return 0;
    if (val < 0) return -1;
}

ll bs(ll x)
{
    ll curr = maxv;
    int lou = 0, haj = convex.size() - 1, mid;
    while (haj - lou > 2)
    {
        mid = (lou + haj) / 2;
        ll _mid = x * convex[mid].first + convex[mid].second;
        ll _donji = x * convex[mid - 1].first + convex[mid - 1].second;
        ll _veci = x * convex[mid + 1].first + convex[mid + 1].second;
        bool koji = 0;
        if (_donji > _veci) koji = 1;
        if (!koji)
        {
            if (_donji > _mid) return _mid;
            haj = mid;
        }
        else
        {
            if (_veci > _mid) return _mid;
            lou = mid;
        }
    }

    ll mini = maxv;

    for (int i = lou; i <= haj; i++) mini = min(mini, x * convex[i].first + convex[i].second);

    return mini;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> a >> b;
        a = abs(a);
        b = abs(b);
        v1.push_back(make_pair(a, b));
    }

    for (int i = 0; i < v1.size(); i++)
    {
        bool da = 1;
        for (int j = 0; j < v1.size(); j++)
        {
            if (v1[i].first < v1[j].first && v1[i].second <= v1[j].second) da = 0;
            if (v1[i].first <= v1[j].first && v1[i].second < v1[j].second) da = 0;
        }
        if (da) v.push_back(v1[i]);
    }

    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());

    convex.push_back(make_pair(v[0].second, 0));

    for (int i = 0; i < v.size(); i++)
    {
        dp[i] = bs(v[i].first);
        if (i < v.size() - 1)
        {
            while (convex.size() >= 2 && ccw(convex[convex.size() - 2], convex[convex.size() - 1], make_pair(v[i + 1].second, dp[i])) != -1) convex.pop_back();
            convex.push_back(make_pair(v[i + 1].second, dp[i]));
        }
    }

    cout << dp[v.size() - 1] * 4;
}

Compilation message

cover.cpp: In function 'long long int bs(long long int)':
cover.cpp:28:8: warning: unused variable 'curr' [-Wunused-variable]
     ll curr = maxv;
        ^~~~
cover.cpp: In function 'int main()':
cover.cpp:72:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < v1.size(); i++)
                     ~~^~~~~~~~~~~
cover.cpp:75:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < v1.size(); j++)
                         ~~^~~~~~~~~~~
cover.cpp:88:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < v.size(); i++)
                     ~~^~~~~~~~~~
cover.cpp:91:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (i < v.size() - 1)
             ~~^~~~~~~~~~~~~~
cover.cpp: In function 'int ccw(std::pair<long long int, long long int>, std::pair<long long int, long long int>, std::pair<long long int, long long int>)':
cover.cpp:24:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1

120.0 / 120.0

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