Submission #579331

#	Time	Username	Problem	Language	Result	Execution time	Memory
579331		perchuts	Aliens (IOI16_aliens)	C++17	0 / 100	1 ms	300 KiB

aliens

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define pb push_back
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define f first
#define s second
using namespace std;
#include "aliens.h"
using ll = long long;
using ull = unsigned long long;
using ii = pair<int,int>;
using iii = tuple<int,int,int>;

const int inf = 2e9+1;
const int mod = 1e9+7;
const int maxn = 1e5+100;

template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }

vector<pair<ll,ll>>pareto;

bool pode(pair<ll,ll>x,pair<ll,ll>y,pair<ll,ll>z){
    return (y.s-x.s)*(z.f-y.f)>=(y.s-z.s)*(x.f-y.f);
}

pair<ll,ll> solve(ll lambda){
    //CHT
    deque<pair<pair<ll,ll>,ll>>lines;
    int n = sz(pareto);
    //dp[i] = min(dp[j-1]+(x_j)^2-2*y_i*x_j) + y_i^2 - lambda
    //f_j(i) = ai+b => a = -2*x_j, b = dp[j-1] + (x_j)^2
    //embutir na dp tudo que precisar, depois tirar

    lines.push_back({{2ll*pareto[0].f,pareto[0].f*pareto[0].f-2ll*pareto[0].f},0});//dummy point
    // printf("+ %d %d\n",lines.back().f.f,lines.back().f.s);
    for(int i=0;i<n;++i){
        auto [x,y] = pareto[i];
        // cout<<x<<" "<<y<<endl;
        while(sz(lines)>=2&&lines[0].f.f*(-y)+lines[0].f.s>=lines[1].f.f*(-y)+lines[1].f.s){
            // printf("- %lld %lld\n",lines.front().f.f,lines.front().f.s);
            lines.pop_front();
        }
        ll dpi = lines.front().f.f*(-y)+lines.front().f.s + y*y + 1ll + 2ll*y + lambda;
        ll qnt = lines.front().s + 1ll;
        //embutir o necessario na dp
        if(i!=n-1){
            dpi += pareto[i+1].f*pareto[i+1].f - 2*pareto[i+1].f
            - (max(0ll,y-pareto[i+1].f+1ll))*(max(0ll,y-pareto[i+1].f+1ll));
            pair<pair<ll,ll>,ll>atual = {{2*pareto[i+1].f,dpi},qnt};
            while(sz(lines)>=2&&pode(atual.f,lines[sz(lines)-2].f,lines.back().f))
                lines.pop_back();
            lines.pb(atual);
            // printf("+ %lld %lld\n",lines.back().f.f,lines.back().f.s);
        }else return {dpi,qnt};
    }
    return {0,0};
}

ll take_photos(int n, int m, int k, vector<int> r1, vector<int> c) {
    vector<ii>v(n);
    for(int i=0;i<n;++i){  
        ++r1[i], ++c[i];
        if(r1[i]<=c[i])v[i] = {r1[i],c[i]};
        else v[i] = {m-r1[i]+1,m-c[i]+1};
    }
    sort(all(v));
    for(int i=0;i<n;++i){
        // cout<<v[i].f<<" "<<v[i].s<<endl;
        if(pareto.empty()||pareto.back().second<v[i].s){
            if(!pareto.empty()&&pareto.back().first==v[i].f)pareto.pop_back();
            pareto.push_back(v[i]);
        }
    }
    //Lagrange opt.
    ll l = 0, r = 1e12;//max delta = 1e12 porque m<=1e6, logo lambda <= 1e12
    while(l<r){
        ll md = (l+r)/2;
        pair<ll,ll>cur = solve(md);
        if(cur.s>k)l = md+1;
        else r = md;
    }   
    pair<ll,ll>res = solve(r);
    return res.f-res.s*r;
}

// int main() {
//     int n, m, k;
//     assert(3 == scanf("%d %d %d", &n, &m, &k));
//     std::vector<int> r(n), c(n);
//     for (int i = 0; i < n; i++) {
//         assert(2 == scanf("%d %d", &r[i], &c[i]));
//     }
//     long long ans = take_photos(n, m, k, r, c);
//     printf("%lld\n", ans);
//     return 0;
// }

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