Submission #999254

#	Time	Username	Problem	Language	Result	Execution time	Memory
999254		imarn	Aliens (IOI16_aliens)	C++14	100 / 100	192 ms	8396 KiB

aliens

#include<bits/stdc++.h>
//#include "game.h"
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define vp vector<pii>
using namespace std;
struct deal{
    ll x,y,z;
};
long double slope(deal x,deal y){
    return ((long double)x.y-y.y)/(y.x-x.x);
}
pll dp[100005];
vector<pll>pt;
pll solve(ll x,int n){
    deque<deal>dq;dq.pb({-2*(pt[0].f-1),(pt[0].f-1)*(pt[0].f-1),0});
    for(int i=0;i<n;i++){
        while(dq.size()>1&&slope(dq[0],dq[1])<pt[i].s)dq.pop_front();
        dp[i] = {dq[0].x*pt[i].s+pt[i].s*pt[i].s+dq[0].y+x,dq[0].z+1};
        if(i==n-1)continue;deal tmp = {-2*(pt[i+1].f-1),(pt[i+1].f-1)*(pt[i+1].f-1)+dp[i].f-max(1ll*0,pt[i].s-pt[i+1].f+1)*max(1ll*0,pt[i].s-pt[i+1].f+1),dp[i].s};
        while(dq.size()>1&&slope(dq[dq.size()-2],dq.back())>slope(dq.back(),tmp))dq.pop_back();
        dq.pb(tmp);
    }return dp[n-1];
}
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
    for(int i=0;i<n;i++){
        if(r[i]>c[i])swap(r[i],c[i]);
        pt.pb({c[i],-r[i]});
    }sort(all(pt));
    stack<pll>st;
    for(auto it : pt){
        while(!st.empty()&&(st.top().s>=-it.s||st.top().f==it.f))st.pop();
        st.push({it.f,-it.s});
    }n=st.size();while(!pt.empty())pt.pop_back();
    while(!st.empty())pt.pb({st.top().s,st.top().f}),st.pop();
    reverse(all(pt));ll le=0,re=1e18;
    while(le<re){
        ll md=(le+re)>>1;
        if(solve(md,n).s<=k)re=md;
        else le=md+1;
    }return solve(le,n).f-le*k;
}

Compilation message (stderr)

aliens.cpp: In function 'std::pair<long long int, long long int> solve(long long int, int)':
aliens.cpp:27:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   27 |         if(i==n-1)continue;deal tmp = {-2*(pt[i+1].f-1),(pt[i+1].f-1)*(pt[i+1].f-1)+dp[i].f-max(1ll*0,pt[i].s-pt[i+1].f+1)*max(1ll*0,pt[i].s-pt[i+1].f+1),dp[i].s};
      |         ^~
aliens.cpp:27:28: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   27 |         if(i==n-1)continue;deal tmp = {-2*(pt[i+1].f-1),(pt[i+1].f-1)*(pt[i+1].f-1)+dp[i].f-max(1ll*0,pt[i].s-pt[i+1].f+1)*max(1ll*0,pt[i].s-pt[i+1].f+1),dp[i].s};
      |                            ^~~~

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