Submission #173928

#	Time	Username	Problem	Language	Result	Execution time	Memory
173928		gs18103	Aliens (IOI16_aliens)	C++14	60 / 100	2064 ms	616248 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define em emplace
#define all(v) v.begin(), v.end()

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const int MAX = 101010;
const int INF = 1e9;
const ll LINF = 1e18;
const int mod = 1e9+7;

vector <pll> line;
double cross(pll a, pll b) {return (double)(b.se - a.se) / (a.fi - b.fi);}

void add_line(pll l) {
    while(line.size() >= 2) {
        pll l1 = line[line.size()-2], l2 = line[line.size()-1];
        if(cross(l1, l2) < cross(l2, l)) break;
        line.pop_back();
    }
    line.eb(l);
}

//solution for nk log n
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
    vector <pll> tarr, arr;
    vector < vector <ll> > dp;
    dp.resize(k+3);
    for(int i = 0; i < n; i++) {
        if(r[i] < c[i]) swap(r[i], c[i]);
        r[i]++;
        tarr.eb(r[i], c[i]);
    }
    sort(all(tarr));
    arr.eb(0, -1);
    for(int i = 0; i < n; i++) {
        while(!arr.empty() && arr.back().se >= tarr[i].se) arr.pop_back();
        arr.eb(tarr[i]);
    }
    n = arr.size() - 1;
    k = min(n, k);
    dp[1].resize(n+1);
    for(int i = 1; i <= n; i++) dp[1][i] = (arr[i].fi - arr[1].se) * (arr[i].fi - arr[1].se);
    for(int i = 2; i <= k; i++) {
        dp[i].resize(n+1);
        int idx = 0;
        while(!line.empty()) line.pop_back();
        add_line(make_pair(-2*arr[1].se, arr[1].se * arr[1].se));
        for(int j = 1; j <= n; j++) {
            while(idx + 1 < line.size() && cross(line[idx], line[idx+1]) <= (double)arr[j].fi) idx++;
            dp[i][j] = arr[j].fi * arr[j].fi + line[idx].fi * arr[j].fi + line[idx].se;
            if(j < n) add_line(make_pair(-2*arr[j+1].se, arr[j+1].se * arr[j+1].se + dp[i-1][j] - max(0LL, arr[j].fi-arr[j+1].se) * max(0LL, arr[j].fi - arr[j+1].se)));
        }
    }
    return dp[k][n];
}

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:57:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(idx + 1 < line.size() && cross(line[idx], line[idx+1]) <= (double)arr[j].fi) idx++;
                   ~~~~~~~~^~~~~~~~~~~~~

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