Submission #622700

#	Time	Username	Problem	Language	Result	Execution time	Memory
622700		Lucpp	Aliens (IOI16_aliens)	C++17	60 / 100	2062 ms	9924 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e12+1;
const ll CINF = 1e6+1;

struct Lin{
    ll a, b; // a*x+b
    ll l, r;
    Lin(ll a_, ll b_, ll l_ = -CINF, ll r_ = CINF): a(a_), b(b_), l(l_), r(r_) {}
    ll eval(ll x) {return a*x+b;}
};
ll sect(Lin f1, Lin f2){
    return (f2.b-f1.b) / (f1.a-f2.a);
}
deque<Lin> q;
void add(Lin f){
    while(!q.empty() && q.back().eval(q.back().l) >= f.eval(q.back().l)) q.pop_back();
    if(!q.empty()){
        q.back().r = sect(q.back(), f);
        f.l = q.back().r+1;
    }
    q.push_back(f);
}
ll qry(ll x){
    while(x > q.front().r) q.pop_front();
    return q.front().eval(x);
}

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

ll take_photos(int n, int m, int k, vector<int> r, vector<int> c){
    m--; // suppress warning
    vector<pair<int, int>> v;
    for(int i = 0; i < n; i++){
        v.emplace_back(min(r[i], c[i]), -max(r[i], c[i]));
    }
    sort(v.begin(), v.end());
    vector<pair<ll, ll>> a;
    for(int i = 0; i < n; i++){
        if(a.empty() || a.back().second < -v[i].second) a.emplace_back(v[i].first, -v[i].second);
    }
    n = (int)a.size();
    vector<ll> dp(n, INF);
    for(int h = 0; h < k; h++){
        q.clear();
        add(Lin(-2*a[0].first, sq(a[0].first)-2*a[0].first));
        for(int i = 0; i < n-1; i++){
            ll b = sq(a[i+1].first)-2*a[i+1].first - sq(max(0ll,a[i].second-a[i+1].first+1)) + dp[i];
            add(Lin(-2*a[i+1].first, b));
        }
        vector<ll> dp2(n);
        for(int i = 0; i < n; i++){
            dp2[i] = sq(a[i].second+1) + qry(a[i].second);
        }
        dp = dp2;
    }
    return dp[n-1];
}

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