Submission #97025

#	Time	Username	Problem	Language	Result	Execution time	Memory
97025		onjo0127	Aliens (IOI16_aliens)	C++11	25 / 100	2062 ms	9344 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define fi first
#define se second

long long D[509][100009];

inline long long p(long long x) { return x*x; }

long long DP(vector<pii>& A, int K) {
    int N = A.size(); K = min(K, N);
    for(int i=0; i<=K; i++) for(int j=0; j<N; j++) D[i][j] = 1LL * 1e18;
    for(int i=0; i<N; i++) D[1][i] = p(A[i].se - A[0].fi + 1);
    for(int i=2; i<=K; i++) {
        for(int j=0; j<N; j++) {
            for(int k=0; k<j; k++) {
                D[i][j] = min(D[i][j], D[i-1][k] + p(A[j].se - A[k+1].fi + 1) - p(max(0, A[k].se - A[k+1].fi + 1)));
            }
        }
    }
    return D[K][N-1];
}

long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
    vector<pii> A, B;
    for(int i=0; i<n; i++) {
        if(r[i] > c[i]) swap(r[i], c[i]);
        A.push_back({r[i], c[i]});
    }
    sort(A.begin(), A.end(), [&](pii P, pii Q) {
        if(P.se == Q.se) return P.fi > Q.fi;
        return P.se < Q.se;
    });
    for(int i=0; i<n; i++) {
        while(B.size() && B.back().fi >= A[i].fi) B.pop_back();
        B.push_back(A[i]);
    }
    return DP(B, k);
}

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