Submission #789238

#	Time	Username	Problem	Language	Result	Execution time	Memory
789238		fatemetmhr	Aliens (IOI16_aliens)	C++17	12 / 100	75 ms	468 KiB

aliens

//  ~ Be Name Khoda ~  //

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

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  1e6   + 10;
const int maxn5 =  1e5   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   + 7;
const ll  inf   =  1e18;

int n;

vector <pair<ll, ll>> av;
ll dp[2][maxn5];

namespace cht{

    int pt = 0, best;
    pair <ll, pair<ll, ll>> a[maxn5]; // {st, {cons, shib}}
    ll last = inf;

    void clear(){
        pt = 0;
        best = 0;
        last = inf;
    }

    ll inter(pair <ll, ll> a, pair <ll, ll> b){
        return (a.fi - b.fi) / (b.se - a.se) + ((a.fi - b.fi) % (b.se - a.se) > 0);
    }

    void add(ll cons, ll x){
        while(pt && inter(a[pt - 1].se, {cons, x}) <= a[pt - 1].fi)
            pt--;
        a[pt] = {-inf, {cons, x}};
        if(pt)
            a[pt].fi = inter(a[pt - 1].se, a[pt].se);
        pt++;
        //cout << "WA " << a[best + 1].fi << ' ' << a[pt - 1].fi << endl;
        //cout << "added " << pt << ' ' << best << ' ' << last << ' ' << a[pt - 1].fi << ' ' << a[best].fi << ' ' << a[best + 1].fi << ' ' << a[pt - 1].se.fi << ' ' << a[pt - 1].se.se << endl;
    }

    ll get_max(ll x){
        best = min(best, pt - 1);
        //cout << "here " << best << ' ' << a[best].fi << ' ' << x << endl;
        while(best + 1 < pt && a[best + 1].fi <= x)
            best++;
        //cout << "in " << x << ' ' << best << endl;
        return a[best].se.fi + a[best].se.se * x;
    }
}

void solve(int x){
    //cout << "********** " << x << endl;
    x &= 1;
    //cht::clear();
    //cht::add(-(av[0].fi * av[0].fi), av[0].fi);
    for(int i = 0; i < n; i++){
        dp[x][i] = (av[i].se - av[0].fi + 1) * (av[i].se - av[0].fi + 1);
        for(int j = 0; j < i; j++)
            dp[x][i] = min(dp[x][i], dp[x^1][j] + (av[i].se - av[j + 1].fi + 1) * (av[i].se - av[j + 1].fi + 1));
        continue;
        dp[x][i] = (av[i].se + 1) * (av[i].se + 1) - cht::get_max(2 * (av[i].se + 1));
        //cout << "hey " << i << ' ' << dp[x][i] << endl;
        if(i + 1 < n)
            cht::add(-(dp[x ^ 1][i] + av[i + 1].fi * av[i + 1].fi), av[i + 1].fi);
    }
}

vector <pair<int, int>> pt;
bool rem[maxn5];

long long take_photos(int N, int m, int k, std::vector<int> r, std::vector<int> c) {
    n = N;
    for(int i =0 ; i < n; i++) if(r[i] > c[i])
        swap(r[i], c[i]);
    for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) if(i != j){
        if(r[j] <= r[i] && c[j] >= c[i] && (r[i] != r[j] || c[i] != c[j] || j < i))
            rem[i] = true;
    }
    for(int i =0 ; i < n; i++) if(!rem[i])
        av.pb({r[i], c[i]});
    n = av.size();
    sort(all(av));
    /*
    for(int i = 0; i < n; i++)
        pt.pb({min(r[i], c[i]), max(r[i], c[i])});
    sort(all(pt));
    for(int i = 0; i < n; i++){
        while(av.size() && av.back().fi == pt[i].fi && av.back().se <= pt[i].se)
            av.pop_back();
        if(av.size() && av.back().se >= pt[i].se)
            continue;
        av.pb(pt[i]);
    }
    */
    /*
    for(int i = 0; i < n; i++)
        cout << av[i].fi << ' ' << av[i].se << endl;
    //*/
    for(int i = 0; i < n; i++)
        dp[0][i] = inf;
    for(int i = 1; i <= k; i++)
        solve(i);
    return dp[k & 1][n - 1];
    return 0;
}

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