Submission #426165

# Submission time Handle Problem Language Result Execution time Memory
426165 2021-06-13T14:48:46 Z 79brue Aliens (IOI16_aliens) C++14
4 / 100
9 ms 332 KB
#include <bits/stdc++.h>
#include "aliens.h"

using namespace std;

typedef long long ll;

int n, m, k;
ll x[500002], y[500002];

void makeArr(vector<int>&, vector<int>&);
pair<ll, int> calc(ll);

ll take_photos(int N, int M, int K, vector<int> r, vector<int> c){
    m = M, k = K;
    makeArr(r, c);
    k = min(n, k);

    assert(calc(0).second == n);
    assert(calc(1e12*2+1).second == 1);

    ll L = 0, R = 1e12+5, ans = 1e12;
    while(L < R){
        ll M = (L+R)>>1;
        if(calc(M*2+1).second <= k) ans = M+1, R = M;
        else L = M+1;
    }

    ll ret = LLONG_MAX;
    for(ll lambda = max(ans*2-300, 0LL); lambda <= ans*2+300; lambda++){
        auto x = calc(lambda);
        if(x.second > k) continue;
        ret = min(ret, x.first - lambda*(x.second-1));
    }
    return ret;
}

void makeArr(vector<int> &r, vector<int> &c){
    vector<pair<int, int> > vec;
    int N = (int)r.size();
    for(int i=0; i<N; i++){
        if(r[i] > c[i]) swap(r[i], c[i]);
        vec.push_back(make_pair(r[i], c[i]));
    }
    sort(vec.begin(), vec.end(), [&](pair<int, int> &x, pair<int, int> &y){
        return x.second < y.second;
    });

    vector<pair<int, int> > stk;
    for(int i=0; i<N; i++){
        if(!stk.empty() && stk.back().second == vec[i].second && stk.back().first <= vec[i].first) continue;
        while(!stk.empty() && stk.back().first >= vec[i].first) stk.pop_back();
        stk.push_back(vec[i]);
    }

    n = (int)stk.size();
    for(int i=1; i<=n; i++) x[i] = stk[i-1].first, y[i] = stk[i-1].second;
}

ll quot(ll a, ll b){
    if(a>=0) return a/b;
    return a/b - !!(a%b);
}

struct Line{
    ll a, b; long double start; int cnt;
    Line(ll a, ll b, int cnt): a(a), b(b), cnt(cnt){}
    Line(ll a, ll b, long double start, int cnt): a(a), b(b), start(start), cnt(cnt){}

    ll val(ll x){
        return a*x+b;
    }

    ll cross(const Line &r)const{
        ll A = r.a - a;
        ll B = r.b - b;
        assert(A >= 0);
        return -B/A;
    }
};

ll DP[500002];
int cnt[500002];
vector<Line> vec;
int pnt = 0;

pair<ll, int> calc(ll lambda){
    for(int i=1; i<=n; i++){
        DP[i] = (y[i] - x[1] + 1) * (y[i] - x[1] + 1);
        cnt[i] = 1;
    }
    vec.clear();
    vec.push_back(Line(2, 3e12, -1e18, 0));

    for(int i=1; i<=n; i++){
        while(pnt >= (int)vec.size() || vec[pnt].start > y[i]) --pnt;
        while(pnt+1 < (int)vec.size() && y[i] >= vec[pnt+1].start) ++pnt;

        ll val = vec[pnt].val(y[i]) + y[i]*y[i] + lambda;
        if(DP[i] > val){
            DP[i] = val;
            cnt[i] = vec[pnt].cnt + 1;
        }

        if(i==n) break;
        Line tmp = Line(-(x[i+1]-1) * 2, (x[i+1]-1) * y[i] * 2 - y[i] * y[i] + DP[i], cnt[i]);
        if(x[i+1] > y[i]) tmp = Line(-(x[i+1]-1) * 2, (x[i+1]-1)*(x[i+1]-1) + DP[i], cnt[i]);

        while((int)vec.size() >= 2 && vec.back().start - 1e-12 > tmp.cross(vec[(int)vec.size()-1])) vec.pop_back();
        tmp.start = tmp.cross(vec.back());
        vec.push_back(tmp);
    }

    return make_pair(DP[n], cnt[n]);
}
# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Correct answer: answer = 4
2 Correct 1 ms 204 KB Correct answer: answer = 4
3 Correct 1 ms 204 KB Correct answer: answer = 4
4 Correct 1 ms 204 KB Correct answer: answer = 12
5 Correct 1 ms 204 KB Correct answer: answer = 52
6 Correct 1 ms 204 KB Correct answer: answer = 210
7 Correct 1 ms 332 KB Correct answer: answer = 88
8 Correct 1 ms 204 KB Correct answer: answer = 7696
9 Correct 1 ms 204 KB Correct answer: answer = 1
10 Correct 1 ms 332 KB Correct answer: answer = 2374
11 Correct 1 ms 332 KB Correct answer: answer = 9502
12 Correct 1 ms 204 KB Correct answer: answer = 49
13 Correct 2 ms 332 KB Correct answer: answer = 151
14 Correct 2 ms 332 KB Correct answer: answer = 7550
15 Correct 1 ms 332 KB Correct answer: answer = 7220
16 Correct 2 ms 332 KB Correct answer: answer = 7550
17 Correct 1 ms 300 KB Correct answer: answer = 10000
18 Correct 1 ms 204 KB Correct answer: answer = 10000
19 Correct 1 ms 332 KB Correct answer: answer = 624
20 Correct 1 ms 204 KB Correct answer: answer = 10000
# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Correct answer: answer = 1
2 Correct 1 ms 332 KB Correct answer: answer = 4
3 Correct 1 ms 204 KB Correct answer: answer = 1
4 Correct 1 ms 204 KB Correct answer: answer = 5
5 Correct 1 ms 204 KB Correct answer: answer = 41
6 Correct 1 ms 204 KB Correct answer: answer = 71923
7 Correct 7 ms 332 KB Correct answer: answer = 77137
8 Incorrect 9 ms 332 KB Wrong answer: output = 942, expected = 764
9 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Correct answer: answer = 4
2 Correct 1 ms 204 KB Correct answer: answer = 4
3 Correct 1 ms 204 KB Correct answer: answer = 4
4 Correct 1 ms 204 KB Correct answer: answer = 12
5 Correct 1 ms 204 KB Correct answer: answer = 52
6 Correct 1 ms 204 KB Correct answer: answer = 210
7 Correct 1 ms 332 KB Correct answer: answer = 88
8 Correct 1 ms 204 KB Correct answer: answer = 7696
9 Correct 1 ms 204 KB Correct answer: answer = 1
10 Correct 1 ms 332 KB Correct answer: answer = 2374
11 Correct 1 ms 332 KB Correct answer: answer = 9502
12 Correct 1 ms 204 KB Correct answer: answer = 49
13 Correct 2 ms 332 KB Correct answer: answer = 151
14 Correct 2 ms 332 KB Correct answer: answer = 7550
15 Correct 1 ms 332 KB Correct answer: answer = 7220
16 Correct 2 ms 332 KB Correct answer: answer = 7550
17 Correct 1 ms 300 KB Correct answer: answer = 10000
18 Correct 1 ms 204 KB Correct answer: answer = 10000
19 Correct 1 ms 332 KB Correct answer: answer = 624
20 Correct 1 ms 204 KB Correct answer: answer = 10000
21 Correct 1 ms 204 KB Correct answer: answer = 1
22 Correct 1 ms 332 KB Correct answer: answer = 4
23 Correct 1 ms 204 KB Correct answer: answer = 1
24 Correct 1 ms 204 KB Correct answer: answer = 5
25 Correct 1 ms 204 KB Correct answer: answer = 41
26 Correct 1 ms 204 KB Correct answer: answer = 71923
27 Correct 7 ms 332 KB Correct answer: answer = 77137
28 Incorrect 9 ms 332 KB Wrong answer: output = 942, expected = 764
29 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Correct answer: answer = 4
2 Correct 1 ms 204 KB Correct answer: answer = 4
3 Correct 1 ms 204 KB Correct answer: answer = 4
4 Correct 1 ms 204 KB Correct answer: answer = 12
5 Correct 1 ms 204 KB Correct answer: answer = 52
6 Correct 1 ms 204 KB Correct answer: answer = 210
7 Correct 1 ms 332 KB Correct answer: answer = 88
8 Correct 1 ms 204 KB Correct answer: answer = 7696
9 Correct 1 ms 204 KB Correct answer: answer = 1
10 Correct 1 ms 332 KB Correct answer: answer = 2374
11 Correct 1 ms 332 KB Correct answer: answer = 9502
12 Correct 1 ms 204 KB Correct answer: answer = 49
13 Correct 2 ms 332 KB Correct answer: answer = 151
14 Correct 2 ms 332 KB Correct answer: answer = 7550
15 Correct 1 ms 332 KB Correct answer: answer = 7220
16 Correct 2 ms 332 KB Correct answer: answer = 7550
17 Correct 1 ms 300 KB Correct answer: answer = 10000
18 Correct 1 ms 204 KB Correct answer: answer = 10000
19 Correct 1 ms 332 KB Correct answer: answer = 624
20 Correct 1 ms 204 KB Correct answer: answer = 10000
21 Correct 1 ms 204 KB Correct answer: answer = 1
22 Correct 1 ms 332 KB Correct answer: answer = 4
23 Correct 1 ms 204 KB Correct answer: answer = 1
24 Correct 1 ms 204 KB Correct answer: answer = 5
25 Correct 1 ms 204 KB Correct answer: answer = 41
26 Correct 1 ms 204 KB Correct answer: answer = 71923
27 Correct 7 ms 332 KB Correct answer: answer = 77137
28 Incorrect 9 ms 332 KB Wrong answer: output = 942, expected = 764
29 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Correct answer: answer = 4
2 Correct 1 ms 204 KB Correct answer: answer = 4
3 Correct 1 ms 204 KB Correct answer: answer = 4
4 Correct 1 ms 204 KB Correct answer: answer = 12
5 Correct 1 ms 204 KB Correct answer: answer = 52
6 Correct 1 ms 204 KB Correct answer: answer = 210
7 Correct 1 ms 332 KB Correct answer: answer = 88
8 Correct 1 ms 204 KB Correct answer: answer = 7696
9 Correct 1 ms 204 KB Correct answer: answer = 1
10 Correct 1 ms 332 KB Correct answer: answer = 2374
11 Correct 1 ms 332 KB Correct answer: answer = 9502
12 Correct 1 ms 204 KB Correct answer: answer = 49
13 Correct 2 ms 332 KB Correct answer: answer = 151
14 Correct 2 ms 332 KB Correct answer: answer = 7550
15 Correct 1 ms 332 KB Correct answer: answer = 7220
16 Correct 2 ms 332 KB Correct answer: answer = 7550
17 Correct 1 ms 300 KB Correct answer: answer = 10000
18 Correct 1 ms 204 KB Correct answer: answer = 10000
19 Correct 1 ms 332 KB Correct answer: answer = 624
20 Correct 1 ms 204 KB Correct answer: answer = 10000
21 Correct 1 ms 204 KB Correct answer: answer = 1
22 Correct 1 ms 332 KB Correct answer: answer = 4
23 Correct 1 ms 204 KB Correct answer: answer = 1
24 Correct 1 ms 204 KB Correct answer: answer = 5
25 Correct 1 ms 204 KB Correct answer: answer = 41
26 Correct 1 ms 204 KB Correct answer: answer = 71923
27 Correct 7 ms 332 KB Correct answer: answer = 77137
28 Incorrect 9 ms 332 KB Wrong answer: output = 942, expected = 764
29 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Correct answer: answer = 4
2 Correct 1 ms 204 KB Correct answer: answer = 4
3 Correct 1 ms 204 KB Correct answer: answer = 4
4 Correct 1 ms 204 KB Correct answer: answer = 12
5 Correct 1 ms 204 KB Correct answer: answer = 52
6 Correct 1 ms 204 KB Correct answer: answer = 210
7 Correct 1 ms 332 KB Correct answer: answer = 88
8 Correct 1 ms 204 KB Correct answer: answer = 7696
9 Correct 1 ms 204 KB Correct answer: answer = 1
10 Correct 1 ms 332 KB Correct answer: answer = 2374
11 Correct 1 ms 332 KB Correct answer: answer = 9502
12 Correct 1 ms 204 KB Correct answer: answer = 49
13 Correct 2 ms 332 KB Correct answer: answer = 151
14 Correct 2 ms 332 KB Correct answer: answer = 7550
15 Correct 1 ms 332 KB Correct answer: answer = 7220
16 Correct 2 ms 332 KB Correct answer: answer = 7550
17 Correct 1 ms 300 KB Correct answer: answer = 10000
18 Correct 1 ms 204 KB Correct answer: answer = 10000
19 Correct 1 ms 332 KB Correct answer: answer = 624
20 Correct 1 ms 204 KB Correct answer: answer = 10000
21 Correct 1 ms 204 KB Correct answer: answer = 1
22 Correct 1 ms 332 KB Correct answer: answer = 4
23 Correct 1 ms 204 KB Correct answer: answer = 1
24 Correct 1 ms 204 KB Correct answer: answer = 5
25 Correct 1 ms 204 KB Correct answer: answer = 41
26 Correct 1 ms 204 KB Correct answer: answer = 71923
27 Correct 7 ms 332 KB Correct answer: answer = 77137
28 Incorrect 9 ms 332 KB Wrong answer: output = 942, expected = 764
29 Halted 0 ms 0 KB -