Submission #923813

#	Time	Username	Problem	Language	Result	Execution time	Memory
923813		velislavgarkov	Aliens (IOI16_aliens)	C++14	60 / 100	1135 ms	1048576 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 {
    long long l;
    long long r;
    bool friend operator < (Interval a, Interval b) {
        if (a.l==b.l) return a.r>b.r;
        return a.l<b.l;
    }
};
struct Prava {
    long long k;
    long long n;
    double x;
};
vector <Prava> env[MAXN];
int br[MAXN];
Interval b[MAXN];
vector <Interval> a;
vector <long long> dp[MAXN];
double intersection(long long k1, long long n1, long long k2, long long n2) {
    double dk, dn;
    dk=k1-k2;
    dn=n2-n1;
    return dn/dk;
}
void add_prava(int ind, long long k, long long n) {
    while (env[ind].size()>1) {
        double x=intersection(env[ind].back().k,env[ind].back().n,k,n);
        if (x>env[ind].back().x) break;
        env[ind].pop_back();
    }
    if (env[ind].empty()) {
        env[ind].push_back({k,n,-INF});
    }
    double x=intersection(env[ind].back().k,env[ind].back().n,k,n);
    env[ind].push_back({k,n,x});
}
void move_br(int ind, double x) {
    br[ind]=min(br[ind],(int)env[ind].size()-1);
    while (br[ind]<env[ind].size() && env[ind][br[ind]].x<=x) br[ind]++;
    br[ind]--;
}
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({-2,-2});
    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;
        a[i].l--;
    }
    dp[0][0]=0;
    long long dif;
    add_prava(0,-2*a[1].l,a[1].l*a[1].l);
    for (int i=1;i<=n;i++) {
        for (int j=min(i,k);j>=1;j--) {
            move_br(j-1,a[i].r);
            if (env[j-1].empty()) {
                cout << "error\n";
                continue;
            }
            dp[i][j]=env[j-1][br[j-1]].n+env[j-1][br[j-1]].k*a[i].r+a[i].r*a[i].r;
            dif=a[i].r-a[i+1].l;
            if (dif<0) dif=0;
            //cout << i << ' ' << j << ' ' << dp[i][j] << ' ' << dif << ' ' << env[j-1][br[j-1]].n << ' ' << env[j-1][br[j-1]].k*a[i].r << endl;
            if (i<n) add_prava(j,-2*a[i+1].l,dp[i][j]+a[i+1].l*a[i+1].l-dif*dif);
        }
    }
    return dp[n][k];
}

Compilation message (stderr)

aliens.cpp: In function 'void move_br(int, double)':
aliens.cpp:46:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Prava>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     while (br[ind]<env[ind].size() && env[ind][br[ind]].x<=x) br[ind]++;
      |            ~~~~~~~^~~~~~~~~~~~~~~~

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