Submission #606989

#	Time	Username	Problem	Language	Result	Execution time	Memory
606989		MohamedFaresNebili	Aliens (IOI16_aliens)	C++14	100 / 100	190 ms	6572 KiB

aliens

#include <bits/stdc++.h>
/// #pragma GCC optimize ("Ofast")
/// #pragma GCC target ("avx2")
/// #pragma GCC optimize("unroll-loops")

            using namespace std;

            using ll = long long;
            using ld = long double;

            #define ff first
            #define ss second
            #define pb push_back
            #define all(x) (x).begin(), (x).end()
            #define lb lower_bound

            const int MOD = 998244353;

            struct line{
                ll m = 0, c = 0, k = 0;
                line(ll _m, ll _c, ll _k) { m = _m, c = _c, k = _k; }
                ll calc(ll x) { return m * x + c; }
                bool slope(line A, line B) {
                    return (A.c - c) * (A.m - B.m) < (B.c - A.c) * (m - A.m);
                }
            };

            struct convex{
                deque<line> S;
                void update(line l) {
                    while(S.size() > 1) {
                        line A = S.back();
                        line B = S[S.size() - 2];
                        if(B.slope(A, l)) break;
                        S.pop_back();
                    }
                    S.push_back(l);
                }

                pair<ll, ll> query(ll x) {
                    while(S.size() > 1 &&
                    S[0].calc(x) > S[1].calc(x))
                        S.pop_front();
                    return {S[0].calc(x), S[0].k};
                }
            };

            ll sq(ll x) { return x * x; }

            int N, X[100001], Y[100001];

            pair<ll, ll> can(ll v) {
                convex C;
                C.update(line(-X[1], sq(X[1]), 0));
                for(int l = 1; l <= N; l++) {
                    pair<ll, ll> p = C.query(2 * Y[l] + 2);
                    ll dp = p.first + sq(Y[l] + 1) + v;
                    if(l == N) return {dp, p.second + 1};
                    ll m = -X[l + 1];
                    ll c = dp - sq(max(0, Y[l] + 1 - X[l + 1])) + sq(X[l + 1]);
                    ll k = p.second + 1;
                    C.update(line(m, c, k));
                }
                return {0, 0};
            }

            bool comp(pair<ll, ll> A, pair<ll, ll> B) {
                if(A.first != B.first)
                    return A.first < B.first;
                return A.second > B.second;
            }

            long long take_photos(int n, int M, int K, vector<int> r, vector<int> c) {
                N = n; vector<pair<ll, ll>> C;
                for(int l = 0; l < N; l++) {
                    if(r[l] > c[l]) swap(r[l], c[l]);
                    C.push_back({r[l], c[l]});
                }
                sort(C.begin(), C.end(), comp);
                int cur = 1;
                for(int l = 0; l < N; l++) {
                    int U = C[l].ff, V = C[l].ss;
                    if(cur == 1 || U < X[cur - 1] || V > Y[cur - 1])
                        X[cur] = U, Y[cur++] = V;
                }
                N = cur - 1;
                ll lo = 0, hi = 1e15, res = -1;
                while(lo <= hi) {
                    ll md = (lo + hi) / 2;
                    if(can(md).ss <= K)
                        res = md, hi = md - 1;
                    else lo = md + 1;
                }
                pair<ll, ll> p = can(res);
                return p.first - 1LL * K * res;
            }

• Subtask 1: 4 / 4
• Subtask 2: 12 / 12
• Subtask 3: 9 / 9
• Subtask 4: 16 / 16
• Subtask 5: 19 / 19
• Subtask 6: 40 / 40