Submission #172810

#	Time	Username	Problem	Language	Result	Execution time	Memory
172810		Mercenary	Aliens (IOI16_aliens)	C++14	0 / 100	9 ms	9720 KiB

aliens

#include<bits/stdc++.h>
#define taskname "A"
#define pb push_back
#define mp make_pair
#ifndef LOCAL
#include "aliens.h"
#endif // LOCAL
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<ll,ll> ii;
const int maxn = 2e5 +5;
const int logn = 20;

struct point{
    ld x , y;
    point(){};
    point(ld x , ld y):x(x) , y(y){};
    point operator - (const point & other){
        return point(x - other.x , y - other.y);
    }
    ld operator * (const point & other){
        return x * other.y - y * other.x;
    }
};
pair<point,int> a[maxn];
ii b[maxn];
ll dp[maxn];
int cnt[maxn];
ll sqr(ll x){
    return x * x;
}
void Solve(int n , int val){
    int m = 0 , p = 1;
    b[0] = mp(-1,-1);
    for(int i = 1 ; i <= n ; ++i){
        auto add = [&](pair<point,int> x){
            while(m >= 2 && (a[m - 1].first - a[m].first) * (x.first - a[m].first) >= 0){
                if(p == m)--p;
                --m;
            }
            a[++m] = x;
        };
        add(mp(point(-2*b[i].first,sqr(b[i].first)+dp[i - 1]+sqr(max(0ll,b[i-1].second-b[i].first+1))),i-1));
        while(p < m && a[p].first.x * (b[i].second + 1) + a[p].first.y >
              a[p + 1].first.x * (b[i].second + 1) + a[p + 1].first.y)++p;
        cnt[i] = cnt[a[p].second] + 1;
        dp[i] = a[p].first.x * (b[i].second + 1) + a[p].first.y + sqr(b[i].second + 1) + val;
    }
}

long long take_photos(int n, int m, int k,vector<int> r, vector<int> c) {
    for(int i = 0 ; i < n ; ++i){
        if(r[i] > c[i])swap(r[i],c[i]);
        b[i + 1] = mp(r[i] , c[i]);
    }
    sort(b + 1 , b + n + 1);
    int cnt = 0;
    for(int i = 1 ; i <= n ; ++i){
        if(cnt > 0 && b[cnt].first == b[i].first)b[cnt].second = b[i].second;
        else b[++cnt] = b[i];
    }
    n = cnt;
    int l = 0 , h = m;
    while(l <= h){
        int mid = l + h >> 1;
        Solve(n , mid);
        if(::cnt[n] > k)l = mid + 1;
        else h = mid - 1;
    }
    Solve(n,l);
//    cout << ::cnt[n] << endl;
    return dp[n] - (ll)k * l;
}

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:71:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = l + h >> 1;
                   ~~^~~

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