Submission #298364

#	Time	Username	Problem	Language	Result	Execution time	Memory
298364		zoooma13	Aliens (IOI16_aliens)	C++14	4 / 100	1 ms	288 KiB

aliens

#include "bits/stdc++.h"
#include "aliens.h"
using namespace std;

bool query = 0;
struct line{
    long long m ,b;
    mutable function <const line*()> succ;
    bool operator<(const line&rhs) const{
        if(!query)
            return m < rhs.m;
        const line *s = succ();
        return s ? (b-s->b) < rhs.m*(s->m-m) : 0;
    }
};
struct hull:deque<line>{
    bool bad(iterator y){
        auto z = next(y);
        if(y == begin()){
            if(z == end())
                return 0;
            return (y->m==z->m) && (y->b<=z->b);
        }
        auto x = prev(y);
        if(z == end())
            return (y->m==x->m) && (y->b<=x->b);
        return (1.0)*(x->b-y->b)*(z->m-y->m) >= (1.0)*(y->b-z->b)*(y->m-x->m);
    }
    void add(long long m ,long long b){
        push_back({-m ,-b}); //remove - for max
        auto it = prev(end());
        it -> succ = [=]{ return next(it)==end() ? 0:&*next(it); };
        if(bad(it)){
            erase(it);
            return;
        }
        while(next(it) != end() && bad(next(it))) erase(next(it));
        while(it != begin()     && bad(prev(it))) erase(prev(it));
    }
    long long eval(long long x){
        if(empty())
            return -LLONG_MAX;
        query = 1;
        auto l = *lower_bound(begin() ,end() ,line{x,0});
        query = 0;
        return -(l.m*x+l.b); //remove - for max
    }
};

long long sqr(long long num){
    return num*num;
}

long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
    vector <pair<int ,int>> rngs ,po;
    for(int i=0; i<n; i++){
        if(r[i] < c[i])
            swap(r[i] ,c[i]);
        rngs.push_back({c[i] ,-r[i]});
    }
    sort(rngs.begin() ,rngs.end());
    int mx = -1;
    for(auto&r : rngs) if(-r.second > mx){
        po.push_back({r.first ,-r.second+1});
        mx = -r.second;
    }
    po.insert(po.begin() ,make_pair(-1 ,0));

    n = po.size();
    vector <long long> dp(n ,1e18) ,exdp(n ,1e18);
    dp[0] = 0 ,exdp[0] = 0;
    while(k--){
        swap(dp ,exdp);
        hull h;
        for(int i=1; i<n; i++){
            h.add(-2*po[i].first ,exdp[i-1] + sqr(po[i].first) - sqr(max(0 ,po[i-1].second-po[i].first)));
            dp[i] = sqr(po[i].second) + h.eval(po[i].second);
            ///for(int j=0; j<i; j++)
               /// dp[i] = min(dp[i] ,exdp[j] + sqr(po[i].second-po[j+1].first+1) - sqr(max(0 ,po[j].second-po[j+1].first+1)));
        }
    }

    return dp.back();
}

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