Submission #1023126

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023126		parsadox2	Aliens (IOI16_aliens)	C++17	60 / 100	212 ms	182348 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define shib first
#define arz  second
using namespace std;
 
const int N = 5e4 + 10 , K = 110 , M = 1e9;
const long long inf = 1e18;
long long dp[N][K] , val[N][K];
 
vector <pair<long long , pair<int , long long>>> cht;
 
long long tav(long long x)
{
    if(x < 0)
        return 0;
    return 1LL * x * x;
}
 
void Reset()
{
    cht.clear();
    cht.push_back(make_pair(0 , make_pair(0 , inf)));
}
 
long long saghf(long long sor , long long mak)
{
    if(mak < 0)
        sor *= -1;
    mak = abs(mak);
    if(sor < 0)
        return sor / mak;
    return (sor + mak - 1) / mak;
}
 
long long insec(pair<int , long long> od , pair<int , long long> nw)
{
    if(od.shib == nw.shib)
        return(nw.arz < od.arz ? -M : M);
    long long sor = nw.arz - od.arz , mak = od.shib - nw.shib;
    return saghf(sor , mak);
}
 
void Add_line(pair<int , long long> ln)
{
    while(!cht.empty())
    {
        long long pos = insec(cht.back().S , ln);
        if(pos <= cht.back().F)
            cht.pop_back();
        else
        {
            cht.push_back(make_pair(pos , ln));
            break;
        }
    }
    if(cht.empty())
        cht.push_back(make_pair(0LL , ln));
}
 
long long Get(long long val)
{
    int pos = upper_bound(cht.begin() , cht.end() , make_pair(val , make_pair(M , inf))) - cht.begin() - 1;
    return 1LL * val * cht[pos].S.shib + cht[pos].S.arz;
}
 
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
    vector <pair<int , int>> vec;
    for(int i = 0 ; i < n ; i++)
    {
        if(r[i] > c[i])
            swap(r[i] , c[i]);
        vec.push_back(make_pair(r[i] , c[i]));
    }
    sort(vec.begin() , vec.end());
    vector <pair<int ,int>> all;
    all.push_back(vec[0]);
    for(auto u : vec)
    {
        if(all.back().F == u.F)
        {
            all.pop_back();
            all.push_back(u);
            continue;
        }
        if(u.S > all.back().S)
            all.push_back(u);
    }
    n = all.size();
    for(int i = 0 ; i < n ; i++)
    {
        dp[i][1] = tav(all[i].S - all[0].F + 1);
        if(i + 1 < n)
            val[i][1] = dp[i][1] - tav(all[i].S - all[i + 1].F + 1) + tav(all[i + 1].F);
    }
    for(int j = 2 ; j <= k ; j++)  
    {
        Reset();
        for(int i = 0 ; i < n ; i++)
        {
            dp[i][j] = Get(all[i].S + 1);
            /*for(int x = 0 ; x < i ; x++)
                dp[i][j] = min(dp[i][j] , val[x][j - 1] - 2LL * (all[i].S + 1) * all[x + 1].F);*/
            dp[i][j] += tav(all[i].S + 1);
            dp[i][j] = min(dp[i][j] , dp[i][j - 1]);
            if(i + 1 < n)
            {
                val[i][j] = dp[i][j] - tav(all[i].S + 1 - all[i + 1].F) + tav(all[i + 1].F);
                Add_line({-2 * all[i + 1].F , val[i][j - 1]});
            }
        }
    }
    return dp[n - 1][k];
}

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