Submission #1023918

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023918		vjudge1	Aliens (IOI16_aliens)	C++17	60 / 100	791 ms	1048576 KiB

aliens

#include <bits/stdc++.h>
#include "aliens.h"

using namespace std;

#define sz(s) (int)s.size()
#define mem(a,i) memset(a,i,sizeof(a))
#define pb push_back
#define all(v) v.begin(),v.end()
#define pii pair<int,int>
#define ll long long
#define F first
#define S second
#define ld long double
#define ppb pop_back

const int MAX=1e6+10;
const ll inf=1e16;

vector<int> vec[MAX];
vector<vector<ll>> dp;
int n,m,k;

ll S(int x,int y){
    ll a=x-y+1;
    if(a<=0)return 0;
    return a*a;
}

ld inter(pair<ll,ll> a,pair<ll,ll> b){
    return (a.S-b.S)/(b.F-a.F);
}

struct cht{
    vector<pair<ll,ll>> lines;
    int pos;

    void init(){
        lines.clear();
        pos=0;
    }

    void add(ll k,ll x){
        while(sz(lines)>1&&inter(lines[sz(lines)-2],lines.back())>inter(lines[sz(lines)-2],{k,x}))lines.ppb();
        lines.pb({k,x});
        pos=min(pos,sz(lines)-1);
    }

    ll get(pair<ll,ll> a,ll x){
        return a.F*x+a.S;
    }

    ll get(ll x){
        if(lines.empty()){
            return inf;
        }
        while(pos+1<sz(lines)&&get(lines[pos],x)>get(lines[pos+1],x)){
            pos++;
        }
        return get(lines[pos],x);
    }
}C;

long long take_photos(int N, int M, int K, vector<int> r, vector<int> c) {
    n=N,m=M,k=K;
    vector<int> actr,actc;
    for(int i=0;i<n;i++){
        if(r[i]<c[i]){
            swap(c[i],r[i]);
        }
        vec[r[i]].pb(c[i]);
    }
    for(int i=0;i<m;i++)sort(all(vec[i]));
    stack<int> st;
    for(int i=0;i<m;i++){
        if(vec[i].empty())continue;
        while(!st.empty()&&vec[st.top()][0]>=vec[i][0]){
            st.pop();
        }
        st.push(i);
    }
    vector<pii> pts;
    while(!st.empty()){
        int x=st.top();
        pts.pb({x,vec[x][0]});
        st.pop();
    }
    reverse(all(pts));
    n=sz(pts);
    dp.resize(n);
    for(int i=0;i<n;i++){
        dp[i].resize(k+1);
        for(int j=0;j<=k;j++){
            dp[i][j]=inf;
        }
    }
    for(int i=0;i<n;i++){
        dp[i][1]=S(pts[i].F,pts[0].S);
        if(i!=n-1){
            dp[i][1]-=S(pts[i].F,pts[i+1].S);
        }
    }
    for(int j=2;j<=k;j++){
        C.init();
        for(int i=0;i<n;i++){
            if(i-1>=0)C.add(-2*pts[i].S,dp[i-1][j-1]+pts[i].S*1ll*pts[i].S-2*pts[i].S);
            else C.add(-2*pts[i].S,+pts[i].S*1ll*pts[i].S-2*pts[i].S);
            dp[i][j]=C.get(pts[i].F)+pts[i].F*1ll*pts[i].F+2*pts[i].F+1;
            if(i!=n-1){
                dp[i][j]-=S(pts[i].F,pts[i+1].S);
            }
            dp[i][j]=min(dp[i][j],inf);
        }
    }
    ll ans=inf;
    for(int j=1;j<=k;j++)ans=min(ans,dp[n-1][j]);
    return ans;
}

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