Submission #361889

#	Time	Username	Problem	Language	Result	Execution time	Memory
361889		2fat2code	Aliens (IOI16_aliens)	C++17	0 / 100	1 ms	492 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define fr first
#define sc second
#define rc(s) return cout<<s,0
#define rcc(s) cout<<s,exit(0)

int pt = 0;
vector <pair<int, int>> segments;

void erase_useless(){
    vector <pair<int,int>> tz;
    for(auto it : segments){
        if(!tz.size()){
            tz.push_back(it);
        }
        else{
            auto it1 = tz.back();
            if(it1.fr >= it.fr && it1.sc <= it.sc){
                tz.pop_back();
                tz.push_back(it);
            }
            else if(it.fr >= it1.fr && it.sc <= it1.sc){
                continue;
            }
            else{
                tz.push_back(it);
            }
        }
    }
    segments = tz;
}

struct line{
    int slope, cons;
    long double pbegin;
};

long double intersect(line A, line B){
    return (long double) (B.cons - A.cons) / (A.slope - B.slope);
}

struct CHT{
    vector <line> hull;
    void add(line TZ){
        if(hull.empty()){
            TZ.pbegin = -1.0;
            hull.push_back(TZ);
        }
        else{
            while((int)hull.size() >= 2){
                if(intersect(TZ, hull.back()) <= intersect(hull.back(), hull[(int)hull.size() - 2])){
                    hull.pop_back();
                }
                else{
                    break;
                }
            }
            TZ.pbegin = intersect(TZ, hull.back());
            hull.push_back(TZ);
        }
    }
    int query(double x){
        if(pt == (int)hull.size() - 1){
            return hull[pt].slope * x + hull[pt].cons;
        }
        else{
            while(hull[pt + 1].pbegin <= x){
                ++pt;
            }
            return hull[pt].slope * x + hull[pt].cons;
        }
    }
};

CHT solution;

long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c){
    vector < vector <int>> dp(n + 5, vector <int> (k + 5));
    for(int i=0;i<n;i++){
        segments.push_back({min(r[i], c[i]), max(r[i], c[i])});
    }
    sort(all(segments));
    erase_useless();
    n = (int)segments.size();
    segments.push_back({0, 0});
    for(int i=1;i<=n;i++){
        dp[i][1] = (segments[i - 1].sc - segments[0].fr + 1) * (segments[i - 1].sc - segments[0].fr + 1);
    }
    for(int j=2;j<=k;j++){
        pt = 0;
        solution.hull.clear();
        dp[1][j] = dp[1][j - 1];
        solution.add({2 - 2*segments[1].fr, dp[1][j - 1] + (segments[1].fr - 1) * (segments[1].fr - 1) - max(0, segments[0].sc - segments[1].fr + 1) * max(0, segments[0].sc - segments[1].fr + 1), 0.0});
        for(int i=2;i<=n;i++){
            dp[i][j] = dp[i][j - 1];
            dp[i][j] = min(dp[i][j], solution.query(segments[i - 1].sc) + segments[i - 1].sc * segments[i - 1].sc);
            solution.add({2 - 2*segments[i].fr, dp[i][j-1] + (segments[i].fr - 1) * (segments[i].fr - 1) - max(0, segments[i - 1].sc - segments[i].fr + 1) * max(0, segments[i - 1].sc - segments[i].fr + 1), 0.0});
        }
    }
    return dp[n][k];
}

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