Submission #295444

#	Time	Username	Problem	Language	Result	Execution time	Memory
295444		alexandra_udristoiu	Aliens (IOI16_aliens)	C++14	60 / 100	2093 ms	6776 KiB

aliens

#include "aliens.h"
#include<vector>
#include<algorithm>
#define x first
#define y second
#define DIM 100005
using namespace std;
int n, dq[DIM], num[DIM];
long long d[2][DIM];
pair<int, int> v[DIM];
pair<int, long long> w[DIM];
int cmp(pair<int, int> a, pair<int, int> b){
    if(a.x == b.x){
        return a.y > b.y;
    }
    return a.x < b.x;
}
long long calc(pair<int, long long> p, int i){
    return p.y + p.x * 1LL * i;
}
long long det(pair<int, long long> p1, pair<int, long long> p2, pair<int, long long> p3){
    return (p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y);
}
long long arie(int a, int b){
    if(a < b){
        return 0;
    }
    return (a - b) * 1LL * (a - b);
}

long long take_photos(int N, int m, int k, vector<int> r, vector<int> c) {
    int i, ii, nr, t, p, u;
    long long sol;
    n = N;
    for(i = 1; i <= n; i++){
        v[i].x = min(r[i - 1], c[i - 1]);
        v[i].y = max(r[i - 1], c[i - 1]);
    }
    sort(v + 1, v + n + 1, cmp);
    nr = 1;
    for(i = 2; i <= n; i++){
        if(v[i].y > v[nr].y){
            v[++nr] = v[i];
        }
    }
    for(i = 1; i <= n; i++){
        v[i].x--;
    }
    n = nr;
    for(i = 1; i <= n; i++){
        d[0][i] = (v[i].y - v[1].x) * 1LL * (v[i].y - v[1].x);
    }
    sol = d[0][n];
    k = min(k, n);
    t = 0;
    for(ii = 2; ii <= k; ii++){
        t = 1 - t;
        p = u = 1;
        w[1].x = -2 * v[ii].x;
        w[1].y = v[ii].x * 1LL * v[ii].x + d[1 - t][ii - 1] - arie(v[ii - 1].y, v[ii].x);
        for(i = ii; i <= n; i++){
            while(p < u && calc(w[p], v[i].y) > calc(w[p + 1], v[i].y) ){
                p++;
            }
            d[t][i] = w[p].y + w[p].x * 1LL * v[i].y + v[i].y * 1LL * v[i].y;
            if(i != n){
                w[++u].x = -2 * v[i + 1].x;
                w[u].y = d[1 - t][i] + v[i + 1].x * 1LL * v[i + 1].x - arie(v[i].y, v[i + 1].x);
                while(p + 1 < u && det(w[u - 2], w[u - 1], w[u]) >= 0){
                    u--;
                    w[u] = w[u + 1];
                }
            }
        }
        sol = min(sol, d[t][n]);
    }
    return sol;
}

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