Submission #1102514

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102514		Zero_OP	Aliens (IOI16_aliens)	C++14	25 / 100	2069 ms	22356 KiB

aliens

#include <bits/stdc++.h>
#ifndef LOCAL
    #include "aliens.h"
#endif // LOCAL

using namespace std;
using ll = long long;

#define all(v) begin(v), end(v)
#define compact(v) v.erase(unique(all(v)), end(v)
#define dbg(x) "[" #x " = " << (x) << "]"
#define sz(v) (int)v.size()

template<typename T> bool minimize(T& a, const T& b){
    if(a > b) return a = b, true; return false;
}

template<typename T> bool maximize(T& a, const T& b){
    if(a < b) return a = b, true; return false;
}

const ll inf = 1e18;

struct line{
    ll a, b, cnt, p;
    line(ll a = 0, ll b = 0, ll cnt = 0, ll p = 0) : a(a), b(b), cnt(cnt), p(p) {}
    ll eval(ll x){ return a * x + b; }
};

ll divi(ll a, ll b){
    return a / b - ((a ^ b) < 0 && (a % b) != 0);
}

void isect(line& d1, line& d2){
    if(d1.a == d2.a) d1.p = (d1.b > d2.b ? inf : -inf);
    else d1.p = divi(d2.b - d1.b, d1.a - d2.a);
}

struct ConvexHullTrick{
    deque<line> v;

    ConvexHullTrick() : v() {}

    void init(){
        deque<line>().swap(v);
    }

    void add(line d){
        d.p = inf;
        if(!v.empty()) isect(v.back(), d);

        while((int)v.size() > 1 && v[(int)v.size() - 2].p >= v.back().p){
            v.pop_back();
            isect(v.back(), d);
        }

        v.push_back(d);
    }

    pair<ll, int> query(ll x){
        while((int)v.size() > 1){
            ll l = v[0].eval(x);
            ll r = v[1].eval(x);
            if(l != r){
                if(l > r) v.pop_front();
                if(l < r) break;
            } else{
                if(v[0].cnt > v[1].cnt) v.pop_front();
                else break;
            }
        }

        return {v[0].eval(x), v[0].cnt};
    }

} cht;

ll square(ll x){
    return x * x;
}

long long take_photos(int n, int m, int k, std::vector<int> l, std::vector<int> r) {
    vector<int> diagonal(n);
    for(int i = 0; i < n; ++i){
        if(l[i] > r[i]) swap(l[i], r[i]);
    }

    vector<int> pos(n);
    iota(all(pos), 0);
    sort(all(pos), [&](int i, int j){
        if(l[i] != l[j]) return l[i] < l[j];
        return r[i] > r[j];
    });

    int ptr = 0;
    vector<pair<int, int>> after;
    for(int i : pos){
        int x = l[i], y = r[i];
        if(!after.empty() && after.back().second >= y) continue;
        after.push_back({x, y});
    }

    n = sz(after);
    vector<ll> L(n), R(n);
    for(int i = 0; i < n; ++i){
        tie(L[i], R[i]) = after[i];
        assert(i == 0 || (L[i - 1] <= L[i] && R[i - 1] <= R[i]));
        --L[i]; //for (R[j] - L[i])^2 instead of (R[j] - L[i] + 1)^2
    }

    auto cost = [&](int i, int j){
        --i, --j;
        ll ret = square(R[j] - L[i]);
        if(i > 0) ret -= square(max(0ll, R[i - 1] - L[i]));
        return ret;
    };

    vector<vector<ll>> dp(k + 1, vector<ll>(n + 1, inf));
    dp[0][0] = 0;
    k = min(k, n);
    for(int c = 1; c <= k; ++c){
        for(int i = 1; i <= n; ++i){
            for(int j = 1; j <= i; ++j){
                minimize(dp[c][i], dp[c - 1][j - 1] + cost(j, i));
            }
        }
    }

    ll res = LLONG_MAX;
    for(int c = 1; c <= k; ++c){
        minimize(res, dp[c][n]);
    }

    return res;
}

#ifdef LOCAL
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cout << take_photos(3, 8, 2, {2, 1, 0}, {4, 2, 1}) << '\n';
    cout << take_photos(5, 7, 2, {0, 4, 4, 4, 4}, {3, 4, 6, 5, 6}) << '\n';
    cout << take_photos(2, 6, 2, {1, 4}, {4, 1}) << '\n';

    return 0;
}
#endif //LOCAL

Compilation message (stderr)

aliens.cpp: In function 'bool minimize(T&, const T&)':
aliens.cpp:15:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   15 |     if(a > b) return a = b, true; return false;
      |     ^~
aliens.cpp:15:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   15 |     if(a > b) return a = b, true; return false;
      |                                   ^~~~~~
aliens.cpp: In function 'bool maximize(T&, const T&)':
aliens.cpp:19:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   19 |     if(a < b) return a = b, true; return false;
      |     ^~
aliens.cpp:19:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   19 |     if(a < b) return a = b, true; return false;
      |                                   ^~~~~~
aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:95:9: warning: unused variable 'ptr' [-Wunused-variable]
   95 |     int ptr = 0;
      |         ^~~

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