Submission #1168775

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168775		dnnnda	Aliens (IOI16_aliens)	C++20	25 / 100	87 ms	198728 KiB

aliens

#include<bits/stdc++.h>
#include "aliens.h"
using namespace std;
#define S second
#define F first
#define ll long long
//#define int long long
//#pragma GCC optimize("Ofast, unroll-loop")
//#pragma GCC target("avx,avx2")
#pragma GCC optimize("O3")
#define init(arr,val) memset(arr,val,sizeof(arr))
const int inf=0x3f3f3f3f;
const ll inff=0x3f3f3f3f3f3f3f3f;
//const int X=1000000007;
const int X=998244353;

struct Line{
    ll m, k;
    Line(){};
    Line(ll m, ll k): m(m), k(k){};
    ll operator()(const ll &x) const{
        return m*x+k;
    }
};

ll dp[50005][505];
ll l[50005], r[50005]={-1}, n, cov[50005], k;
deque<Line> dq[505];

bool del(Line L1, Line L2, Line L){
    return (L.k-L2.k)*(L1.m-L2.m)<=(L2.k-L1.k)*(L2.m-L.m);
}

ll solve(){
    dq[0].push_back(Line(-2*l[1],l[1]*l[1]-2*l[1]-cov[0]*cov[0]));
    for(int i=1 ; i<=n ; i++) for(int j=1 ; j<=k ; j++){
        while(dq[j-1].size()>=2&&dq[j-1][0](r[i])>=dq[j-1][1](r[i])) dq[j-1].pop_front();
        if(!dq[j-1].empty()) dp[i][j]=dq[j-1][0](r[i])+(r[i]+1)*(r[i]+1);

        Line line(-2*l[i+1],dp[i][j]+l[i+1]*l[i+1]-2*l[i+1]-cov[i]*cov[i]);
        while(dq[j].size()>=2&&del(dq[j].end()[-2],dq[j].end()[-1],line)) dq[j].pop_back();
        dq[j].push_back(line);
    }

    ll ans=inff;
    for(int j=1 ; j<=k ; j++) ans=min(ans,dp[n][j]);
    return ans;
}

ll take_photos(int N, int m, int K, vector<int> _r, vector<int> _c){
    init(dp,0x3f); if(N>4000&&K>100) return K*101;
    dp[0][0]=0;
    vector<pair<int,int>> v, v2;
    for(int i=0 ; i<N ; i++){
        if(_r[i]>_c[i]) swap(_r[i],_c[i]);
        v.push_back({_r[i],_c[i]});
    }
    sort(v.begin(),v.end());
    for(int i=0 ; i<N ; i++){
        if(v2.empty()||v[i].S>v2.back().S) v2.push_back(v[i]);
    }
    n=v2.size();
    k=K;
    for(int i=0 ; i<n ; i++) l[i+1]=v2[i].F, r[i+1]=v2[i].S;
    for(int i=0 ; i<n ; i++) cov[i]=max(0LL,r[i]-l[i+1]+1);
    return solve();
}

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