Submission #492255

#	Time	Username	Problem	Language	Result	Execution time	Memory
492255		Killer2501	Aliens (IOI16_aliens)	C++14	60 / 100	2078 ms	10168 KiB

aliens

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pll pair<ll, ll>
#define pb push_back
using namespace std;
const int N = 1e5+5;
const int M = 2e5+5;
const ll mod = 1e9+7;
const int base = 400;
const ll inf = 1e16;
ll ans, tong, n, k, a[N], b[N], m, c[N], d[N], t, lab[N], dp[N][2];
vector<pll> adj[N], kq;
string s;
pll p[N];
void cal(int l, int r, int opl, int opr, int j)
{
    if(l > r)return;
    int mid = (l+r)/2;
    int best = mid;
    dp[mid][j] = inf;
    for(int i = opl; i <= min(mid, opr); i ++)
    {
        tong = dp[i-1][j^1] + (p[mid].se-p[i].fi+1)*(p[mid].se-p[i].fi+1);
        if(i > 1)tong -= max(0ll, p[i-1].se-p[i].fi+1)*max(0ll, p[i-1].se-p[i].fi+1);
        if(dp[mid][j] > tong)
        {
            dp[mid][j] = tong;
            best = i;
        }
    }
    cal(l, mid-1, opl, best, j);
    cal(mid+1, r, best, opr, j);
}
bool cmp(pll& x, pll& y)
{
    if(x.fi != y.fi)return x.fi < y.fi;
    return x.se > y.se;
}
ll take_photos(int N, int M, int K, vector<int> r, vector<int> c)
{
    n = N;
    m = M;
    k = K;
    for(int i = 1; i <= n; i ++)
    {
        p[i].fi = r[i-1];
        p[i].se = c[i-1];
        if(p[i].fi > p[i].se)swap(p[i].fi, p[i].se);
    }
    sort(p+1, p+1+n, cmp);
    for(int i = 1; i <= n; i ++)
    {
        if(!kq.empty() && kq.back().se >= p[i].se)continue;
        kq.pb(p[i]);
    }
    n = kq.size();
    for(int i = 1; i <= n; i ++)p[i] = kq[i-1];
    for(int i = 1; i <= n; i ++)dp[i][0] = inf;
    for(int j = 1; j <= k; j ++)
    {
        cal(1, n, 1, n, j&1);
    }
    return dp[n][k&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