Submission #477630

#	Time	Username	Problem	Language	Result	Execution time	Memory
477630		JovanB	Aliens (IOI16_aliens)	C++17	100 / 100	196 ms	6580 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
using ld = long double;
 
const ll INF = 1000000000000000000LL;
const int N = 1000000;
 
struct line{
    ll k, n;
    ll eval(ll x){ return k*x + n; }
    ld intersect(line g){
        return 1.0*(n - g.n)/(g.k - k);
    }
} seg[4*N+5];
 
ll dp[N+5];
int used[N+5];
 
ll presek(pair <ll, ll> a, pair <ll, ll> b){
    ll h = max(0LL, a.second - b.first + 1);
    return h*h;
}
 
void dodaj(deque <pair <line, int>> &q, pair <line, int> k){
    while(q.size() > 1){
        line g;
        int us;
        tie(g, us) = q.back();
        q.pop_back();
        ld x1 = q.back().first.intersect(g);
        ld x2 = g.intersect(k.first);
        if(x1 < x2){
            q.push_back({g, us});
            break;
        }
    }
    q.push_back(k);
}
 
ll query(deque <pair <line, int>> &q, ll x){
    while(q.size() > 1 && q[0].first.eval(x) > q[1].first.eval(x)) q.pop_front();
    return q.front().first.eval(x);
}
 
void solve(vector <pair <ll, ll>> &vec, ll pen){
    int n = vec.size();
    deque <pair <line, int>> q;
    dodaj(q, {{-2*(vec[0].first - 1), vec[0].first*vec[0].first - 2*vec[0].first}, 0});
    for(int i=0; i<n; i++){
        dp[i] = 1 + vec[i].second*vec[i].second + query(q, vec[i].second) - pen;
        used[i] = 1 + q.front().second;
        if(i != n - 1) dodaj(q, {{-2*(vec[i+1].first - 1), vec[i+1].first*vec[i+1].first - 2*vec[i+1].first - presek(vec[i], vec[i+1]) + dp[i]}, used[i]});
    }
    while(!q.empty()) q.pop_back();
}
 
long long take_photos(int n, int m, int k, std::vector<int> _r, std::vector<int> _c) {
    vector <pair <int, int>> points;
    for(int i=0; i<n; i++){
        if(_r[i] > _c[i]) swap(_r[i], _c[i]);
        points.push_back({_r[i] + 1, _c[i] + 1});
    }
    sort(points.begin(), points.end(), [](pair <int, int> a, pair <int, int> b){ if(a.second == b.second) return a.first < b.first; return a.second > b.second; });
    vector <pair <ll, ll>> vec;
    for(auto c : points){
        if(vec.empty() || c.first < vec.back().first) vec.push_back(c);
    }
    reverse(vec.begin(), vec.end());
    solve(vec, 0);
    n = vec.size();
    ll res = dp[n-1];
    if(used[n-1] <= k) return res;
    ll l = -1LL*m*m, r = 1LL*m*m, opt = -1LL*m*m;
    while(l <= r){
        ll mid = (l+r)/2;
        solve(vec, mid);
        if(used[n-1] <= k){
            l = mid + 1;
            opt = mid;
        }
        else r = mid - 1;
    }
    solve(vec, opt);
    return dp[n-1] + opt*k;
}

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