제출 #522404

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
522404		sjoonmin07	Aliens (IOI16_aliens)	C++17	60 / 100	2045 ms	7288 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
 
#define MAXN 100005
#define pb push_back
#define all(v) (v).begin(), (v).end()
typedef long long lld;
 
int N, M, K;
lld D[MAXN], E[MAXN];
int stk[MAXN]; double xpos[MAXN]; int scnt;
struct Z{
    int r, c;
} A[MAXN];
 
lld y_intercept(int n)
{
    lld ret = E[n] + (lld)A[n+1].r*A[n+1].r - 2*A[n+1].r;
    if (A[n+1].r <= A[n].c) ret -= (lld)(A[n].c-A[n+1].r+1)*(A[n].c-A[n+1].r+1);
    return ret;
}
 
double get_cross(int a, int b)
{
    // slope: -2A[i+1].r
    return (y_intercept(b) - y_intercept(a)) / (-2.) / (A[a+1].r - A[b+1].r);
}
 
lld take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c)
{
    M = m, K = k;
    vector <Z> arr;
    for (int i=0;i<n;i++) arr.pb({min(r[i], c[i]), max(r[i], c[i])});
    sort(all(arr), [](const Z &a, const Z &b){
        return a.c != b.c ? a.c < b.c : a.r > b.r;
    });
    for (Z &z: arr){
        while (N && A[N].r >= z.r) N--;
        A[++N] = z;
    }
    K = min(K, N);
    for (int i=1;i<=N;i++) D[i] = (lld)(A[i].c-A[1].r+1)*(A[i].c-A[1].r+1);
    for (int k=2;k<=K;k++){
        for (int i=1;i<=N;i++) E[i] = D[i];
        int pt = 1;
        scnt = 0;
        for (int i=k;i<=N;i++){
            while (scnt && get_cross(stk[scnt], i-1) < xpos[scnt]) scnt--;
            if (pt > scnt) pt = scnt;
            stk[++scnt] = i-1;
            if (scnt == 1) xpos[scnt] = -1e18;
            else xpos[scnt] = get_cross(stk[scnt-1], stk[scnt]);
            while (pt < scnt && xpos[pt+1] < A[i].c) pt++;
            int j = stk[pt];
            D[i] = y_intercept(j) - 2LL*A[j+1].r*A[i].c + (lld)A[i].c*A[i].c + 2*A[i].c + 1;
        }
    }
    return D[N];
}

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