Submission #1292254

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292254		LmaoLmao	Aliens (IOI16_aliens)	C++20	100 / 100	135 ms	22572 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define name "a"
using namespace std;

using ii = pair<long long,long long>;
using aa = array<long long,3>;
using ll = long long;
const int N=1e6+5;
const int MOD=1e9+7;

ll pre[N];
ii dp[N];
ll a[N];
ll b[N];
ll m,n;
vector<ii> v;


double slope(aa a, aa b) {
    return (double)(a[1]-b[1]) / (b[0]-a[0]);
}


void alien(ll delta) {
    deque<aa> q;
    q.push_back({v[1].fi*2,v[1].fi*v[1].fi+delta-pre[1],0});
    int j=0;
    for(int i=1;i<v.size();i++) {
     
        while (q.size() > 1 && slope(q[0], q[1]) < v[i].se) q.pop_front();
        dp[i].fi=q[0][0]*v[i].se+q[0][1]+v[i].se*v[i].se+pre[i];
        dp[i].se=q[0][2]+1;
        if(i<v.size()-1) {
            aa cur={v[i+1].fi*2,dp[i].fi+v[i+1].fi*v[i+1].fi+delta-pre[i+1],dp[i].se};
            while (q.size() > 1 && slope(q[q.size() - 2], q.back()) > slope(q.back(), cur)) q.pop_back();
            q.push_back(cur);

        }
        //cout << dp[i].fi << ' ' << v[i].se << endl;
    }
    return;
}

long long	take_photos(int	M,	int	N,	int	k,	vector<int> R,	vector<int> C) {
    m=M;
    n=N;
    for(ll i=0;i<m;i++) {
        ll x=R[i]+1,y=C[i]+1;
        if(x<y) {
            a[y]=max(a[y],y-x+1);
        }
        else {
            a[x]=max(a[x],x-y+1);
        }
    }
    long long tmp=-1e18;
    for(ll i=n;i>0;i--) {
        if(a[i]-i<=tmp) a[i]=0;
        tmp=max(tmp,(ll)a[i]-i);
        b[i]=a[i];
    }
    v.push_back({0,0});
    for(ll i=1;i<=n;i++) {
        if(a[i]) v.push_back({a[i]-i,i});
    }
    ll skibidi=0;
    for(ll i=1;i<v.size();i++) {
        if(v[i].se-a[v[i].se]<v[i-1].se) {
            ll tmp=v[i-1].se-(v[i].se-a[v[i].se]);
            skibidi+=tmp*tmp;
            pre[i]=tmp*tmp;
        }
        pre[i]+=pre[i-1];
    }
    //cout << skibidi << endl;;

    ll l=0,r=n*n;
    ll ans=0;
    while(l<=r) {
        ll mid = l + r >> 1;
        alien(mid);
        if(dp[v.size()-1].se<=k) {
            ans=mid;
            r=mid-1;
        }
        else {
            l=mid+1;
        }
    }

    alien(ans);
    if(ans==0) {
        return dp[v.size()-1].fi-skibidi;
    }
    else {
        return dp[v.size()-1].fi-ans*k-skibidi;
    }
}

Compilation message (stderr)

aliens.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
aliens_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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