제출 #923794

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
923794		velislavgarkov	Aliens (IOI16_aliens)	C++14	60 / 100	2069 ms	356296 KiB

aliens

#include "aliens.h"
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int MAXN=1e5+10;
const long long INF=1e15;
struct Interval {
    int l;
    int r;
    bool friend operator < (Interval a, Interval b) {
        if (a.l==b.l) return a.r>b.r;
        return a.l<b.l;
    }
};
Interval b[MAXN];
vector <Interval> a;
vector <long long> dp[MAXN];
void dnc(int k, int l, int r, int opl, int opr) {
    if (l>r) return;
    int mid=(l+r)/2;
    dp[mid][k]=INF;
    int curop=-1;
    long long dif1, dif2;
    for (int i=opl;i<=min(mid,opr);i++) {
        dif1=a[mid].r-a[i].l+1;
        dif2=a[i-1].r-a[i].l+1;
        if (dif2<0) dif2=0;
        if (dp[mid][k]>dp[i-1][k-1]+dif1*dif1-dif2*dif2) {
            dp[mid][k]=dp[i-1][k-1]+dif1*dif1-dif2*dif2;
            curop=i;
        }
    }
    //cout << l << ' ' << r << ' ' << mid << ' ' << dp[mid][k] << ' ' << curop << endl;
    dnc(k,l,mid-1,opl,curop);
    dnc(k,mid+1,r,curop,opr);
}
long long take_photos(int n, int m, int k, vector <int> r, vector <int> c) {
    for (int i=0;i<n;i++) {
        b[i].l=min(r[i],c[i]);
        b[i].r=max(r[i],c[i]);
    }
    sort(b,b+n);
    int maxr=b[0].r;
    a.push_back({-1,-1});
    a.push_back(b[0]);
    for (int i=1;i<n;i++) {
        if (b[i].r<=maxr) continue;
        a.push_back(b[i]);
        maxr=b[i].r;
    }
    n=a.size()-1;
    k=min(n,k);
    for (int i=0;i<=n;i++) dp[i].resize(k+1);
    for (int i=1;i<=n;i++) dp[i][0]=INF;
    dp[0][0]=0;
    for (int i=1;i<=k;i++) {
        dnc(i,1,n,1,n);
    }
    return dp[n][k];
}

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