Submission #1027150

#	Time	Username	Problem	Language	Result	Execution time	Memory
1027150		vjudge1	Aliens (IOI16_aliens)	C++17	0 / 100	1016 ms	1048576 KiB

aliens

#include "aliens.h"
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
ll stb[50100][17],rev[50100];
inline ll stbqr(int a,int b){
    int x=31-__builtin_clz(b-a);
    return min(stb[a][x],stb[b-(1<<x)+1][x]);
}
inline ll Gcost(int l,int r){
    ll k=stbqr(l+1,r);
    ll A=max(0ll,rev[r]-k+1);
    ll B=max(0ll,rev[l]-k+1);
    return A*A-B*B;
}
ll dp[50100],dp2[50100];
void dnc(int l,int r,int opl,int opr){
    if(l>r)return;
    int mid=l+r>>1,opt=0;
    dp2[mid]=1e18;
    for(int i=opl;i<mid&&i<=opr;i++){
        ll K=Gcost(i,mid)+dp[i];
        if(K<dp2[mid])dp2[mid]=K,opt=i;
    }
    dnc(l,mid-1,opl,opt);
    dnc(mid+1,r,opt,opr);
}
ll take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
    swap(m,n);
    memset(stb,1,sizeof stb);
    map<int,int>mp;
    int CC=0;
    map<int,int>mp2;
    for(int i=0;i<m;i++){
        r[i]++;c[i]++;
        if(r[i]>c[i]) swap(r[i],c[i]);
        mp[c[i]];
        if(mp2.count(c[i]))
            mp2[c[i]]=min(mp2[c[i]],r[i]);
        else mp2[c[i]]=r[i];
    }
    vector<int>todie;
    int sfc=1e9;
    auto it=mp2.end();
    do {
        it--;
        if(it->second>=sfc)
            todie.push_back(it->first);
        else sfc=it->second;
    }while(it!=mp.begin());
    for(auto i:todie)
        mp.erase(i),mp2.erase(i);
    for(auto&[i,j]:mp)
        rev[j=++CC]=i;
    n=mp.size();
    for(int i=0;i<m;i++)
        stb[mp[c[i]]][0]=min(stb[c[i]][0],(ll)r[i]);
    for(int i=1;i<17;i++)
        for(int j=1;j+(1<<i)<=n+2;j++)
            stb[j][i]=min(stb[j][i-1],stb[j+(1<<i-1)][i-1]);
    memset(dp,1,sizeof dp);
    dp[0]=0;
    while(k--){
        dnc(1,n,0,n);
        for(int i=1;i<=n;i++)
            dp[i]=dp2[i];
    }
    return dp[n];
}

Compilation message (stderr)

aliens.cpp: In function 'void dnc(int, int, int, int)':
aliens.cpp:19:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   19 |     int mid=l+r>>1,opt=0;
      |             ~^~
aliens.cpp: In function 'll take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:60:50: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   60 |             stb[j][i]=min(stb[j][i-1],stb[j+(1<<i-1)][i-1]);
      |                                                 ~^~

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