Submission #295584

#	Time	Username	Problem	Language	Result	Execution time	Memory
295584		alexandra_udristoiu	Aliens (IOI16_aliens)	C++14	100 / 100	321 ms	9464 KiB

aliens

#include "aliens.h"
#include<vector>
#include<algorithm>
#define x first
#define y second
#define DIM 100005
#define eps 0.0001
using namespace std;
int n, dq[DIM], num[DIM];
long double d[DIM];
pair<int, int> v[DIM];
pair<int, long double> 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 double calc(pair<int, long double> p, int i){
    return p.y + p.x * 1LL * i;
}
long double det(pair<int, long double> p1, pair<int, long double> p2, pair<int, long double> 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);
}
int solve(double c){
    int i, p, u;
    p = 1;
    u = 0;
    v[0].y = -100000;
    for(i = 1; i <= n; i++){
        w[i].x = -2 * v[i].x;
        w[i].y = d[i - 1] + v[i].x * 1LL * v[i].x - arie(v[i - 1].y, v[i].x);
        dq[++u] = i;
        while(p + 1 < u && det( w[ dq[u - 2] ], w[ dq[u - 1] ], w[ dq[u] ]) >= 0){
            u--;
            dq[u] = dq[u + 1];
        }
        while(p < u && calc( w[ dq[p] ], v[i].y) > calc(w[ dq[p + 1] ], v[i].y) ){
            p++;
        }
        d[i] = calc(w[ dq[p] ], v[i].y) + v[i].y * 1LL * v[i].y + c;
        num[i] = 1 + num[ dq[p] - 1 ];
    }
    return num[n];
}

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;
    double st, dr, mid;
    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;
    solve(6.6543);
    k = min(k, n);

    st = 0;
    dr = 100000000000.0;
    for(ii = 0; ii < 60; ii++){
        mid = (st + dr) / 2;
        if( solve(mid) >= k ){
            st = mid;
        }
        else{
            dr = mid;
        }
    }
    solve(dr);
    sol = d[n] - dr * k + 0.1;
    return sol;
}

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:54:20: warning: unused variable 't' [-Wunused-variable]
   54 |     int i, ii, nr, t, p, u;
      |                    ^
aliens.cpp:54:23: warning: unused variable 'p' [-Wunused-variable]
   54 |     int i, ii, nr, t, p, u;
      |                       ^
aliens.cpp:54:26: warning: unused variable 'u' [-Wunused-variable]
   54 |     int i, ii, nr, t, p, u;
      |                          ^

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