Submission #1205943

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205943		loiiii12358	Aliens (IOI16_aliens)	C++20	4 / 100	1 ms	328 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long

struct cht{
    deque<pair<int,int>> lines;
    long double intercept(pair<int,int> l1,pair<int,int> l2){
        return (l1.second-l2.second)/(long double)(l2.first-l1.first);
    }
    void add(int m, int c){//slope decreasing
        while(lines.size()>1&&intercept(lines.back(),{m,c})>=intercept(lines.back(),lines[lines.size()-2])){
            lines.pop_back();
        }
        while(!lines.empty()&&intercept(lines.back(),{m,c})<=0){
            lines.pop_back();
        }
        lines.push_back({m,c});
    }
    int query(int x){//query increasing
        while(lines.size()>1&&x>=intercept(lines.front(),lines[1])){
            lines.pop_front();
        }
        return lines.front().first*x+lines.front().second;
    }
};

long long take_photos(int32_t n, int32_t m, int32_t k, std::vector<int32_t> r, std::vector<int32_t> c) {
    vector<int> dp(n+1,1e13),a(n+1,0),b(n+1,0),gc={0},gr={0};
    vector<pair<int,int>> points;
    deque<pair<int,int>> dq;
    int tmp,ans=1e13;
    for(int i=0;i<n;i++){
        if(r[i]>c[i]){
            swap(r[i],c[i]);
        }
        points.push_back({c[i],r[i]});
    }
    sort(points.begin(),points.end());
    for(int i=0;i<points.size();i++){
        while(!dq.empty()&&dq.back().second>=points[i].second){
            dq.pop_back();
        }
        dq.push_back(points[i]);
    }
    for(int i=0;i<dq.size();i++){
        gc.push_back(dq[i].first+1);
        gr.push_back(dq[i].second+1);
    }
    for(int i=0;i<dq.size();i++){
        if(gc[i]-gr[i+1]+1>=0){
            a[i]=2-2*gr[i+1];
            b[i]=(gc[i]+2-2*gr[i+1])*(-gc[i]);
        }else{
            a[i]=2-2*gr[i+1];
            b[i]=(1-gr[i+1])*(1-gr[i+1]);
        }
        // cout << a[i] << ' ' << b[i] << '\n';
    }
    dp[0]=0;
    for(int i=1;i<=k;i++){
        cht now;
        now.add(a[0],b[0]);
        for(int j=1;j<=dq.size();j++){
            tmp=gc[j]*gc[j]+now.query(gc[j]);
            now.add(a[j],b[j]+dp[j]);
            dp[j]=tmp;
            // cout << dp[j] << " \n"[j==dq.size()];
        }
        ans=min(ans,tmp);
    }
    return ans;
}

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: 0 / 12
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40