제출 #224823

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
224823		jhnah917	Aliens (IOI16_aliens)	C++14	25 / 100	2121 ms	439672 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
using namespace std;
 
typedef long long ll;
typedef pair<ll, ll> p;
 
int n, m, k;
ll dp[101010][555];
p a[101010];
vector<p> v;

void init(int N, int M, int K, const vector<int> &R, const vector<int> &C){
    m = M, k = K; v.clear();
    for(int i=0; i<N; i++) v.emplace_back(min(R[i], C[i]), max(R[i], C[i]));
    sort(all(v), [](p a, p b){
        if(a.y != b.y) return a.y < b.y;
        return a.x > b.x;
    });
    n = 0;
    for(auto &i : v){
        while(n && a[n].x > i.x) n--;
        a[++n] = i;
    }
    memset(dp, 0x3f, sizeof dp);
    for(int i=1; i<=n; i++) dp[i][1] = (a[i].y - a[1].x + 1) * (a[i].y - a[1].x + 1);
}
 
ll take_photos(int N, int M, int K, vector<int> R, vector<int> C){
    init(N, M, K, R, C);
    int q = min(n, k);
    
    for(int j=2; j<=q; j++){
        for(int k=j-1; k<n; k++){
            for(int i=k+1; i<=n; i++){
                ll aa = a[i].y - a[k+1].x + 1;
                ll bb = max(0LL, a[k].y - a[k+1].x + 1);
                dp[i][j] = min(dp[i][j], dp[k][j-1] + aa*aa - bb*bb);
            }
        }
    }

    /*cout << n << q << "\n";
    for(int i=1; i<=n; i++){
        for(int j=1; j<=q; j++) cout << dp[i][j] << " ";
        cout << "\n";
    }*/
 
    return dp[n][q];
}

// g++ -O2 -std=c++11 -static -o main grader.cpp aliens.cpp aliens.h

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