제출 #298318

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
298318		zoooma13	Aliens (IOI16_aliens)	C++14	25 / 100	2036 ms	544 KiB

aliens

#include "bits/stdc++.h"
#include "aliens.h"
using namespace std;

long long sqr(long long num){
    return num*num;
}

long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
    vector <pair<int ,int>> rngs ,po;
    for(int i=0; i<n; i++){
        if(r[i] < c[i])
            swap(r[i] ,c[i]);
        rngs.push_back({c[i] ,-r[i]});
    }
    sort(rngs.begin() ,rngs.end());
    int mx = -1;
    for(auto&r : rngs) if(-r.second > mx){
        po.push_back({r.first ,-r.second});
        mx = -r.second;
    }
    po.insert(po.begin() ,make_pair(-1 ,-1));

    n = po.size();
    vector <long long> dp(n ,1e18) ,exdp(n ,1e18);
    dp[0] = 0 ,exdp[0] = 0;
    while(k--){
        swap(dp ,exdp);
        for(int i=1; i<n; i++)
        for(int j=0; j<i; j++)
            dp[i] = min(dp[i] ,exdp[j] + sqr(po[i].second-po[j+1].first+1) - sqr(max(0 ,po[j].second-po[j+1].first+1)));
    }

    return dp.back();
}

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