제출 #520908

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
520908		pokmui9909	Aliens (IOI16_aliens)	C++17	0 / 100	1 ms	300 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using lf = long double;
 
#define x first
#define y second
ll N, M, K;
pair<ll, ll> A[100005];
ll R[100005];
ll C[100005];
ll D[2][100005];
void init(){
    sort(A + 1, A + N + 1, [&](pair<ll, ll> a, pair<ll, ll> b) -> bool{
        if(a.y != b.y) return a.y < b.y;
        else return a.x > b.x;
    });
    ll T = 0;
    for(int i = 1; i <= N; i++){
        while(T && A[T].x >= A[i].x) T--;
        A[++T] = A[i];
    }
    N = T;
    for(int i = 1; i <= N; i++){
        R[i] = A[i].x;
        C[i] = A[i].y;
    }
}
struct Line{
    ll a, b, i;
    ll f(ll x){
        return a * x + b;
    }
};
lf X_cross(Line f, Line g){
    return 1.0 * (f.b - g.b) / (g.a - f.a);
}
 
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
    N = n; M = m; K = k;
    for(int i = 1; i <= n; i++){
        A[i] = {r[i - 1], c[i - 1]};
        A[i].x++; A[i].y++;
        if(A[i].x > A[i].y){
            swap(A[i].x, A[i].y);
        }
    }
    init();
    K = min(K, N);
    for(int i = 1; i <= N; i++){
        D[1][i] = (C[i]-R[1]+1)*(C[i]-R[1]+1);
    }
    for(int i = 2; i <= K; i++){
        ll p = i % 2, q = (i - 1) % 2;
        deque<Line> dq;
        dq.push_back({-2 * R[1], R[1] * R[1] + max(0LL,-R[1]+1)*max(0LL,-R[1]+1)});
        for(int j = 1; j <= N; j++){
            while(dq.size() >= 2 && dq[0].f(C[j] + 1) >= dq[1].f(C[j] + 1)) dq.pop_front();
            D[p][j] = dq[0].f(C[j] + 1);
            D[p][j] += (C[j] + 1) * (C[j] + 1);
            Line f = {-2 * R[j + 1], D[q][j] + R[j + 1] * R[j + 1] + max(0LL,C[j]-R[j+1]+1)*max(0LL,C[j]-R[j+1]+1)};
            while(dq.size() >= 2 && X_cross(f, dq[dq.size() - 2]) >= X_cross(f, dq[dq.size() - 1])) dq.pop_front();
            dq.push_back(f);
        }
    }
    return D[K % 2][N];
}

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