제출 #925975

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
925975		12345678	Aliens (IOI16_aliens)	C++17	12 / 100	67 ms	199316 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const ll nx=5e4+5, inf=LLONG_MAX;

ll dp[505][nx], area[nx];
stack<ll> s;

struct point
{
    ll x, y;
    bool operator< (const point &o) const {
        if (x==o.x) return y>o.y;
        return x<o.x;
    }
} v[nx], p[nx];

struct line
{
    ll m, c, p;
    line(ll m, ll c, ll p): m(m), c(c), p(p){}
};

struct convexhull
{
    deque<line> dq;
    ll div(ll a, ll b)
    {
        if ((a^b)>0||a%b==0) return a/b;
        return a/b-1;
    }
    void add(ll m, ll c)
    {
        line nw=line(m, c, inf);
        while (dq.size()>=2&&div(nw.c-dq[dq.size()-2].c, dq[dq.size()-2].m-nw.m)<=dq[dq.size()-1].p) dq.pop_back();
        if (!dq.empty()) dq.back().p=div(nw.c-dq.back().c,dq.back().m-nw.m);
        dq.push_back(nw);
    }
    ll query(ll x)
    {
        while (x>=dq.front().p) dq.pop_front();
        return dq.front().m*x+dq.front().c;
    }
} cvh;

long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
    for (int i=0; i<n; i++) if (r[i]>c[i]) swap(r[i], c[i]);
    for (int i=1; i<=n; i++) v[i].x=c[i-1], v[i].y=r[i-1];
    sort(v+1, v+n+1);
    for (int i=1; i<=n; i++)
    {
        while (!s.empty()&&v[s.top()].y>=v[i].y) s.pop();
        s.push(i);
    }
    n=s.size();
    while (!s.empty()) p[s.size()]=v[s.top()], s.pop();
    for (int i=2; i<=n; i++) if (p[i-1].x>=p[i].y) area[i]=(p[i-1].x-p[i].y+1)*(p[i-1].x-p[i].y+1);
    for (int i=1; i<=n; i++) dp[1][i]=(p[i].x-p[1].y+1)*(p[i].x-p[1].y+1);
    //for (int i=1; i<=n; i++) cout<<i<<' '<<area[i]<<' '<<p[i].x<<' '<<p[i].y<<' '<<dp[1][i]<<'\n';
    k=min(k, n);
    for (int i=2; i<=k; i++)
    {
        while (cvh.dq.size()>0) cvh.dq.pop_back();
        for (int j=i; j<=n; j++)
        {
            dp[i][j]=LLONG_MAX;
            for (int k=j; k>=i; k--) dp[i][j]=min(dp[i][j], dp[i-1][k-1]+(p[j].x-p[k].x+1)*(p[j].x-p[k].x+1));
            //cvh.add(-2*p[j].y, p[j].y*p[j].y-2*p[j].y+1-area[j]+dp[i-1][j-1]);
            //dp[i][j]=cvh.query(p[j].x)+p[j].x*p[j].x+2*p[j].x;
        }
    }
    return dp[k][n];
}

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