Submission #1272952

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272952		kl0989e	Aliens (IOI16_aliens)	C++20	4 / 100	1 ms	348 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define vl vector<ll>
#define pi pair<int, int>
#define pl pair<ll,ll>
#define all(x) (x).begin(),(x).end()

struct cht {
    vector<pl> stk;
    vi cnt;
    int pt=0;

    void add(ll a, ll b, int c) {
        while (stk.size()>1 && (1.0*stk[stk.size()-2].se-b)/(a-stk[stk.size()-2].fi) <= (1.0*stk.back().se-stk[stk.size()-2].se)/(stk[stk.size()-2].fi-stk.back().fi)) {
            stk.pop_back();
            cnt.pop_back();
        }
        stk.pb({a,b});
        cnt.pb(c);
        if (pt>=stk.size()) {
            pt=stk.size()-1;
        }
    }

    pl get(ll x) {
        while (pt<stk.size()-1 && ((__int128_t)(x)*stk[pt].fi+stk[pt].se)>=((__int128_t)(x)*stk[pt+1].fi+stk[pt+1].se)) {
            pt++;
        }
        return {x*stk[pt].fi+stk[pt].se,cnt[pt]};
    }
};

vector<pl> po;

pl solve(int n, int k, ll p) {
    cht chts;
    chts.add(2*(1-po[0].fi),(1-po[0].fi)*(1-po[0].fi),0);
    vl dp(n+1,2e12);
    vl cnt(n+1,0);
    dp[0]=0;
    for (int i=1; i<=n; i++) {
        dp[i]=po[i-1].se*po[i-1].se+chts.get(po[i-1].se).fi+p;
        cnt[i]=chts.get(po[i-1].se).se+1;
        ll sub=0;
        if (i!=n && po[i-1].se>=po[i].fi) {
            sub=(po[i-1].se-po[i].fi+1)*(po[i-1].se-po[i].fi+1);
        }
        if (i!=n) {
            chts.add(2*(1-po[i].fi),dp[i]-sub+(1-po[i].fi)*(1-po[i].fi),cnt[i]);
        }
    }
    return {dp[n]-cnt[n]*p,cnt[n]};
    /*vector<cht> chts(k+1);
    for (int i=0; i<k; i++) {
        chts[i].add(2*(1-po[0].fi),(1-po[0].fi)*(1-po[0].fi));
    }
    vector<vl> dp(n+1,vl(k+1,2e12));
    dp[0][0]=0;
    for (int i=1; i<=n; i++) {
        for (int j=k; j>=1; j--) {
            dp[i][j]=min(dp[i][j],po[i-1].se*po[i-1].se+chts[j-1].get(po[i-1].se));
            ll sub=0;
            if (i!=n && po[i-1].se>=po[i].fi) {
                sub=(po[i-1].se-po[i].fi+1)*(po[i-1].se-po[i].fi+1);
            }
            if (i!=n) {
                chts[j].add(2*(1-po[i].fi),dp[i][j]-sub+(1-po[i].fi)*(1-po[i].fi));
            }
        }
    }
    return *min_element(all(dp[n]));*/
}

ll take_photos(int n, int m, int k, vi r, vi c) {
    vector<pl> tpo(n);
    vl pmx(n);
    for (int i=0; i<n; i++) {
        tpo[i].fi=min(r[i],c[i]);
        tpo[i].se=max(r[i],c[i]);
    }
    sort(all(tpo));
    po.pb(tpo[0]);
    for (int i=0; i<n; i++) {
        if (po.back().fi==tpo[i].fi) {
            po.back().se=tpo[i].se;
        }
        else if (po.back().se<tpo[i].se) {
            po.pb(tpo[i]);
        }
    }
    n=po.size();
    k=min(n,k);
    ll tl=0,tr=1ll*m*m;
    ll ans=2e12;
    while (tl<=tr) {
        ll m=tl+(tr-tl)/2;
        pl s=solve(n,k,m);
        ans=min(ans,s.fi);
        if (s.se>k) {
            tl=m+1;
        }
        else {
            tr=m-1;
        }
    }
    return ans;
}

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: 0 / 12
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40