Submission #312641

#	Time	Username	Problem	Language	Result	Execution time	Memory
312641		aZvezda	Aliens (IOI16_aliens)	C++14	100 / 100	540 ms	11748 KiB

aliens

//#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
typedef long double ld;
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ld mod = 1e12 + 7;
const ll MAX_CORD = 1e6 + 10;
const ld eps = 1e-2;
#define out(x) "{" << (#x) << ": " << x << "} "

struct Line {
    ld a, b, delta;
    long double p;
    Line() {}
    Line(ld _a, ld _b, ld _delta) {a = _a; b = _b; delta = _delta;}
    ld y(ld x) {return a * x + b;}
    long double getWhere(const Line &other) {
        if(a == other.a) {
            return -mod;
        } else {
            return (long double)(b - other.b) / (long double)(other.a - a);
        }
    }
};

struct LineContainer {
    deque<Line> lines;
    void addLine(Line curr) {
        while(!lines.empty() && lines.back().getWhere(curr) <= lines.back().p) {
            lines.pop_back();
        }
        if(lines.empty()) {
            curr.p = -mod;
        } else {
            curr.p = lines.back().getWhere(curr);
        }
        lines.push_back(curr);
    }
    pair<ld, int> get(ll x) {
        while(lines.size() > 1 && lines[1].p <= x) {
            lines.pop_front();
        }
        return {lines.front().y(x), lines.front().delta};
    }
    void clear() {
        while(!lines.empty()) {lines.pop_back();}
    }
};

const ll MAX_N = 1e5 + 10;
ll n, m, k;
vector<pair<ll, ll> > points;
ld dp[MAX_N];
ll delta[MAX_N];
LineContainer lc;

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

ll calculate(ld del) {
    lc.clear();
    dp[0] = delta[0] = 0;
    lc.addLine(Line(-2ll * points[1].second, points[1].second * points[1].second + del, 0));
    for(ll i = 1; i < points.size(); i ++) {
        auto best = lc.get(points[i].first);
        dp[i] = best.first + points[i].first * points[i].first;
        delta[i] = best.second + 1;
        if(i != points.size() - 1) {
            lc.addLine(Line(-2ll * points[i + 1].second, dp[i] - toSqr(max(points[i].first - points[i + 1].second, 0ll)) + toSqr(points[i + 1].second) + del, delta[i]));
        }

    }
    return delta[points.size() - 1];
}


long long take_photos(int N, int M, int K, std::vector<int> r, std::vector<int> c) {
    n = N; m = M; k = K;
    for(ll i = 0; i < n; i ++) {
        if(r[i] < c[i]) {
            points.push_back({c[i], -r[i]});
        } else {
            points.push_back({r[i], -c[i]});
        }
    }
    sort(points.begin(), points.end());
    vector<pair<ll, ll> > cpy;
    ll mn = mod;
    for(ll i = n - 1; i >= 0; i --) {
        if(-points[i].second < mn) {
            mn = -points[i].second;
            cpy.push_back({points[i].first + 1, -points[i].second});
        }
    }
    k = min(k, (ll)cpy.size());
    cpy.push_back({0, 0});
    points = cpy;
    reverse(points.begin(), points.end());
    ld lft = -mod, rght = mod;

    for(int iter = 0; iter < 60; iter ++) {
        ld m = (lft + rght) / 2.;
        if(calculate(m) > k) {
            lft = m;
        } else {
            rght = m;
        }
    }
    calculate(rght);
    return round(dp[cpy.size() - 1] - (ld) max(k, delta[cpy.size() - 1]) * rght);
}

Compilation message (stderr)

aliens.cpp: In function 'll calculate(ld)':
aliens.cpp:72:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for(ll i = 1; i < points.size(); i ++) {
      |                   ~~^~~~~~~~~~~~~~~
aliens.cpp:76:14: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         if(i != points.size() - 1) {
      |            ~~^~~~~~~~~~~~~~~~~~~~

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