Submission #1027135

#	Time	Username	Problem	Language	Result	Execution time	Memory
1027135		vjudge1	Aliens (IOI16_aliens)	C++17	12 / 100	27 ms	2704 KiB

aliens

#include "aliens.h"
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int stb[50100][17],rev[50100];
inline int 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){
    int k=stbqr(l+1,r);
    ll A=(rev[r]-k+1);
    ll B=max(0,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++){
        int 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);
    for(int i=1;i<=n;i++)
        for(int k=0;k<17;k++)
            stb[i][k]=i+1;
    map<int,int>mp;
    int CC=0;
    for(int i=0;i<m;i++){
        r[i]++;c[i]++;
        if(r[i]>c[i]) swap(r[i],c[i]);
        mp[c[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],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),swap(dp,dp2);
    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:47:50: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   47 |             stb[j][i]=min(stb[j][i-1],stb[j+(1<<i-1)][i-1]);
      |                                                 ~^~

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