Submission #241500

#	Time	Username	Problem	Language	Result	Execution time	Memory
241500		Hehehe	Aliens (IOI16_aliens)	C++14	Compilation error	0 ms	0 KiB

aliens

#include<bits/stdc++.h>
#include "aliens.h"
using namespace std;
typedef long long ll;
#define all(a) (a).begin(), (a).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define rc(s) return cout<<s,0
#define pi pair <int, int>
#define sz(x) (int)((x).size())
#define int long long

const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};

const ll inf = 2e9;
const ll mod = 1e9 + 7;
const int N = 100010 + 11;
const int NMAX = 1e4 + 11;
const ll INF64 = 2e18;
const double eps = 1e-14;
const double PI = acos(-1);

//ifstream in(".in");
//ofstream out(".out");

struct interval{
    int l,r;
};

interval a[N];
int dp[N], cnt[N], n, m, k;

struct line{
    int a,b, cnt;
    int val(int x){
        return a*x + b;
    }
};

double cross(line a, line b){
    return (a.b - b.b)/(b.a - a.a);
}

bool cmp(interval x, interval y){
    if(x.l != y.l)return (x.l < y.l);
    return (x.r > y.r);
}

int P(int x){
    return x * x;
}

void solve(int lambda){

    deque<line>dq;

    for(int i = 1; i <= n; i++){

        line cur = {-2*a[i].l, P(a[i].l) + dp[i - 1] - P(max(0ll, a[i - 1].r - a[i].l + 1ll)), cnt[i - 1] + 1ll};

        while(sz(dq) >= 2 && cross(cur,dq[sz(dq) - 1]) < cross(dq[sz(dq) - 1],dq[sz(dq) - 2]))dq.pop_back();

        dq.push_back(cur);

        while(sz(dq) >= 2 && cross(dq[0],dq[1]) < (a[i].r + 1))dq.pop_front();

        cnt[i] = dq.front().cnt;

        dp[i] = dq.front().val(a[i].r + 1) + P(a[i].r + 1) + lambda;

    }

}

long long take_photos (int N, int M, int K, std::vector <int> r, std::vector <int> c){

    n = N, m = M, k = K;

    for(int i = 0; i < n; i++){
        a[i + 1].l = min(r[i], c[i]);
        a[i + 1].r = max(r[i], c[i]);
    }

    sort(a + 1, a + n + 1, cmp);

    a[0].l = a[0].r = -1;

    int L = -1, R = -1, cur = 0;
    for(int i = 1; i <= n; i++){
        if(!(L <= a[i].l && a[i].r <= R)){
            a[++cur] = a[i];
            L = a[i].l;
            R = a[i].r;
        }
    }

    n = cur;

    k = min(k, n);

    int st = 0ll, dr = INF64;
    while(st <= dr){
        int mid = (st + dr) >> 1;
        solve(mid);
        if(cnt[n] > k)st = mid + 1;else dr = mid - 1;
    }

    solve(st);

    return dp[n] - st*k;
}

Compilation message (stderr)

/tmp/cc7l2uJ2.o: In function `main':
grader.cpp:(.text.startup+0xdf): undefined reference to `take_photos(int, int, int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status