Submission #211822

#	Time	Username	Problem	Language	Result	Execution time	Memory
211822		lyc	Aliens (IOI16_aliens)	C++14	0 / 100	5 ms	384 KiB

aliens

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

#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
#define SZ(x) ((int)(x).size())

#define SQ(x) ((long long)(x)*(x))

struct Line {
    int m;
    long long c;
    int u;
    pair<long long,int> eval(int x) {
        return make_pair((long long)m*x + c, u);
    }
};
struct ConvexHull {
    deque<Line> dq;
    long double intersect(Line a, Line b) {
        return (long double)(a.c-b.c)/(b.m-a.m);
    }
    void add(int m, long long b, int u) {
        Line l = {m,b,u};
        while (!dq.empty() && dq.front().m >= m) dq.pop_front();
        while (SZ(dq) > 1 && intersect(l,dq[0]) >= intersect(dq[0],dq[1])) dq.pop_front();
        dq.push_front(l);
    }
    pair<long long,int> query(int x) {
        while (SZ(dq) > 1 && intersect(dq[SZ(dq)-2],dq.back()) >= x) dq.pop_back();
        return dq.back().eval(x);
    }
};

pair<long long,int> solve(int n, int m, vector<array<int,2>>& p, long long lcost) {
    pair<long long,int> dp[n+1];
    dp[n] = make_pair(0,0);

    ConvexHull ch;
    RFOR(i,n-1,0){
        long long overlap = (p[i+1][0] <= p[i][1] ? SQ(p[i][1]+1-p[i+1][0]) : 0);
        ch.add(-2*(p[i][1]+1), dp[i+1].first + SQ(p[i][1]+1) - overlap, dp[i+1].second);
        dp[i] = ch.query(p[i][0]);
        dp[i].first += SQ(p[i][0]) + lcost;
        dp[i].second += 1;

        //dp[j+1].first + SQ(p[j][1]+1) - 2*(p[j][1]+1)*p[i][0] + SQ(p[i][0])
        //              - SQ(p[j][1]+1-p[j+1][0]) if overlap
        //cout << "dp " << i << " :: " << dp[i].first << ' ' << dp[i].second << endl;
    }
    return dp[0];
}

long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
    vector<array<int,2>> p;
    FOR(i,0,n-1){
        if (r[i] > c[i]) p.push_back(array<int,2>{c[i],r[i]});
        else p.push_back(array<int,2>{r[i],c[i]});
    }

    sort(p.begin(),p.end());
    p.push_back(array<int,2>{1000005,1000005});
    //for(auto&x:p){
    //    cout<<x[0]<<' '<<x[1]<<endl;
    //}

    long long lo = 0, hi = 1e12+10;
    //long long lo = 0, hi = 0;
    while (hi-lo > 1) {
        long long mid = (lo+hi)/2;
        auto res = solve(n,m,p,mid);
        if (res.second <= k) hi = mid;
        else lo = mid;
    }
    //cout << "hi " << hi << endl;
    auto ans = solve(n,m,p,hi);
    //cout << ans.first << " " << ans.second << endl;
    return ans.first - ans.second * hi;
}

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