Submission #923757

#	Time	Username	Problem	Language	Result	Execution time	Memory
923757		velislavgarkov	Aliens (IOI16_aliens)	C++14	25 / 100	2017 ms	9432 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];
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);
    long long dif1, dif2;
    dp[0][0]=0;
    for (int i=1;i<=n;i++) {
        dp[i][0]=INF;
        for (int j=1;j<=k;j++) {
            dp[i][j]=dp[i][j-1];
            for (int p=i;p>=1;p--) {
                dif1=a[i].r-a[p].l+1;
                dif2=a[p-1].r-a[p].l+1;
                if (dif2<0) dif2=0;
                dp[i][j]=min(dp[i][j],dp[p-1][j-1]+dif1*dif1-dif2*dif2);
            }
        }
    }
    return dp[n][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