Submission #1176403

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176403		AlgorithmWarrior	Aliens (IOI16_aliens)	C++20	100 / 100	182 ms	19648 KiB

aliens

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

using namespace std;

long long const INF=1e18;

struct interval{
    int l,r;
    bool operator<(interval ot){
        if(l!=ot.l)
            return l<ot.l;
        return r>ot.r;
    }
}intv[100005];

long long diag[2000005];

void maxself(long long& x,long long val){
    if(x<val)
        x=val;
}

void minself(long long& x,long long val){
    if(x>val)
        x=val;
}

long long p2(int nr){
    return 1LL*nr*nr;
}

struct line{
    long long a,b;
    int cnt;
};

long double inters(line l1,line l2){
    return 1.0*(l2.b-l1.b)/(l1.a-l2.a);
}

struct answer{
    long long val;
    int cnt;
    bool operator<(answer ot){
        if(val!=ot.val)
            return val<ot.val;
        return cnt>ot.cnt;
    }
};

answer eval(line lin,long long x){
    return {lin.a*x+lin.b,lin.cnt};
}

struct CHT{
    deque<line>deq;
    void init(){
        while(!deq.empty())
            deq.pop_back();
    }
    void add(line lin){
        while(deq.size()>=2 && inters(lin,deq.back())<inters(deq[deq.size()-2],deq.back()))
            deq.pop_back();
        deq.push_back(lin);
    }
    answer query(long long x){
        answer ans={INF,0};
        while(1){
            answer cand=eval(deq[0],x);
            if(cand<ans)
                ans=cand;
            if(deq.size()>=2 && inters(deq[0],deq[1])<=1.0*x)
                deq.pop_front();
            else
                break;
        }
        return ans;
    }
}cht;

answer get_dp(long long lambda,int total){
    cht.init();
    cht.add({-2*intv[1].l,p2(intv[1].l),0});
    int i;
    answer ans;
    for(i=1;i<=total;++i){
        ans=cht.query(intv[i].r);
        ans.val+=p2(intv[i].r)+lambda;
        ++ans.cnt;
        cht.add({-2*intv[i+1].l,p2(intv[i+1].l)-p2(max(0,intv[i].r-intv[i+1].l))+ans.val,ans.cnt});
    }
    return ans;
}

long long take_photos(int n,int m,int k,vector<int>r,vector<int>c){
    int i;
    for(i=0;i<2*m-1;++i)
        diag[i]=-1;
    for(i=0;i<n;++i){
        int lin=r[i];
        int col=c[i];
        maxself(diag[lin+col],abs(lin-col));
    }
    int total=0;
    for(i=0;i<2*m-1;++i)
        if(diag[i]>-1)
            intv[++total]={(i-(int)diag[i])/2,(i+(int)diag[i])/2+1};
    sort(intv+1,intv+total+1);
    int new_total=0;
    intv[0]={-1,-1};
    for(i=1;i<=total;++i)
        if(intv[new_total].r<intv[i].r)
            intv[++new_total]=intv[i];
    total=new_total;
    /// [)
    long long st=0,dr=1e18;
    while(dr-st>1){
        long long mij=(st+dr)/2;
        answer ans=get_dp(mij,total);
        if(ans.cnt>=k)
            st=mij;
        else
            dr=mij;
    }
    return get_dp(st,total).val-st*k;
}

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