Submission #43859

#	Time	Username	Problem	Language	Result	Execution time	Memory
43859		PowerOfNinjaGo	Aliens (IOI16_aliens)	C++14	100 / 100	215 ms	59348 KiB

aliens

//Power Of Ninja Go
#include <bits/stdc++.h>
#ifdef atom
    #include "grader.cpp"
#else
    #include "aliens.h"
#endif
using namespace std;
typedef long long ll; typedef pair<int, int> ii;
#define X first
#define Y second
#define vi vector<int>
#define vii vector< ii >
#define pb push_back
struct line
{
    ll m, b;
    int k;
    line()
    {
        m = 0, b = 4e18; k = 0;
    }
    line(ll _m, ll _b, int _k)
    {
        m = _m; b = _b; k = _k;
    }
    ll f(int x){ return m*x+b; }
};
bool lessthan(line A, line B, int x)
{
    ll y1 = A.f(x), y2 = B.f(x);
    if(y1 != y2) return y1< y2;
    return A.k< B.k;
}
const int maxn = 1e5+5;
const int maxm = 1e6+5;
int n, m;
ll dp[maxn];
int opt[maxn];
vector<line> hull;
int ptr = 0;
bool bad(line &t1, line &t2, line &t3)
{
    return 1.00*(t2.b-t1.b)*(t1.m-t3.m)> 1.00*(t3.b-t1.b)*(t1.m-t2.m);
}
void add(line t)
{
    hull.pb(t);
    while(hull.size()> 2 && bad(hull[hull.size()-3], hull[hull.size()-2], hull.back()))
        hull.erase(hull.end()-2);
    if(ptr>= hull.size()) ptr = hull.size()-1;
    //printf("hull size is %d\n", hull.size());
}
line ask(int x)
{
    while(ptr+1< hull.size() && lessthan(hull[ptr+1], hull[ptr], x)) ptr++;
    return hull[ptr];
}
vii vec, tmp;
vi r, c;
bool cmp(ii A, ii B)
{
    if(A.X != B.X) return A.X< B.X;
    return A.Y> B.Y;
}
pair<long long, int> trial(ll lambda)
{
    ptr = 0;
    hull.clear();
    add(line(-2LL*r[0], 1LL*r[0]*r[0]-2*r[0], 0));
    for(int i = 0; i< n; i++)
    {
        line res = ask(c[i]);
        //printf("use line %lld %lld\n", res.m, res.b);
        opt[i] = res.k+1;
        dp[i] = res.f(c[i])+1LL*c[i]*c[i]+2*c[i]+lambda+1;
        //printf("dp[%d] = %lld\n", i, dp[i]);
        //if(i+1< n) printf("push m = %lld b = %lld\n", -2LL*r[i+1], dp[i]+1LL*r[i+1]*r[i+1]-2*r[i+1]-1LL*mag*mag);
        if(i+1< n)
        {
            int mag = max(0, c[i]-r[i+1]+1);
            add(line(-2LL*r[i+1], dp[i]+1LL*r[i+1]*r[i+1]-2*r[i+1]-1LL*mag*mag, opt[i]));
        }
    }
    return make_pair(dp[n-1], opt[n-1]);
}
long long take_photos(int N, int M, int K, std::vector<int> R, std::vector<int> C)
{
    n = N; m = M;
    for(int i = 0; i< n; i++)
    {
        if(R[i]<= C[i]) vec.pb(ii(R[i], C[i]));
        else vec.pb(ii(C[i], R[i]));
    }
    tmp = vec;
    vec.clear();
    sort(tmp.begin(), tmp.end(), cmp);
    for(auto k : tmp)
    {
        if(vec.empty() || k.Y> vec.back().Y) vec.pb(k);
    }
    n = vec.size();
    for(int i = 0; i< n; i++) r.pb(vec[i].X), c.pb(vec[i].Y);
    //for(int i = 0; i< n; i++) printf("%d %d\n", r[i], c[i]);
    ll lo = 0, hi = 1LL*m*m;
    while(lo< hi)
    {
        ll mid = (lo+hi)/2;
        auto res = trial(mid);
        //printf("%lld: (%lld %d)\n", mid, res.X, res.Y);
        if(res.Y<= K) hi = mid;
        else lo = mid+1;
    }
    //printf("0: %lld %d\n", trial(0).X, trial(0).Y);
    return trial(lo).X-1LL*K*lo;
}

Compilation message (stderr)

aliens.cpp: In function 'void add(line)':
aliens.cpp:51:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(ptr>= hull.size()) ptr = hull.size()-1;
           ^
aliens.cpp: In function 'line ask(int)':
aliens.cpp:56:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(ptr+1< hull.size() && lessthan(hull[ptr+1], hull[ptr], x)) ptr++;
                ^

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