Submission #520924

#	Time	Username	Problem	Language	Result	Execution time	Memory
520924		pokmui9909	Aliens (IOI16_aliens)	C++17	0 / 100	1 ms	204 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 L[100005];
ll R[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;
    A[0] = {-1, -1};
    for(int i = 1; i <= N; i++){
        while(T && A[T].x >= A[i].x) T--;
        if(A[T].y < A[i].y) L[++T] = A[i].x, R[T] = A[i].y;
    }
    N = T;
}
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);
    vector<vector<ll>> D(K + 5, vector<ll>(N + 5, 1e18));
    for(int i = 1; i <= N; i++){
        D[1][i] = (R[i] - L[1] + 1) * (R[i] - L[1] + 1);
    }
    for(int i = 2; i <= K; i++){
        for(int j = 1; j <= N; j++){
            for(int k = 1; k <= i - 1; k++){
                D[i][j] = min(D[i][j], D[i - 1][k] + (R[j]-L[k+1]+1)*(R[j]-L[k+1]+1) - max(0LL,R[k]-L[k+1]+1)*max(0LL,R[k]-L[k+1]+1));
            }
        }
    }
    return D[K][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