Submission #1176192

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176192		AlgorithmWarrior	Aliens (IOI16_aliens)	C++20	25 / 100	4 ms	9288 KiB

aliens

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

using namespace std;

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[1000005];

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;
};

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

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);
    }
    long long query(long long x){
        while(deq.size()>=2 && inters(deq[0],deq[1])<=1.0*x)
            deq.pop_front();
        return deq[0].a*x+deq[0].b;
    }
}cht;

long long take_photos(int n,int m,int k,vector<int>r,vector<int>c){
    int i,j;
    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-diag[i])/2,(i+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;
    vector<vector<long long>>dp(total+5,vector<long long>(k+5,1e18));
    for(i=1;i<=total;++i)
        dp[i][1]=p2(intv[i].r-intv[1].l);
    int lst;
    if(k>total)
        k=total;
    for(j=2;j<=k;++j){
        cht.init();
        cht.add({-2*intv[j].l,p2(intv[j].l)-p2(max(0,intv[j-1].r-intv[j].l))+dp[j-1][j-1]});
        for(i=j;i<=total;++i){
            dp[i][j]=p2(intv[i].r)+cht.query(intv[i].r);
            cht.add({-2*intv[i+1].l,p2(intv[i+1].l)-p2(max(0,intv[i].r-intv[i+1].l))+dp[i][j-1]});
        }
    }
    return dp[total][k];
}

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:69:39: warning: narrowing conversion of '((((long long int)i) - diag[i]) / 2)' from 'long long int' to 'int' [-Wnarrowing]
   69 |             intv[++total]={(i-diag[i])/2,(i+diag[i])/2+1};
      |                            ~~~~~~~~~~~^~
aliens.cpp:69:55: warning: narrowing conversion of '(((((long long int)i) + diag[i]) / 2) + 1)' from 'long long int' to 'int' [-Wnarrowing]
   69 |             intv[++total]={(i-diag[i])/2,(i+diag[i])/2+1};
      |                                          ~~~~~~~~~~~~~^~
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