Submission #201763

#	Time	Username	Problem	Language	Result	Execution time	Memory
201763		oscarsierra12	Aliens (IOI16_aliens)	C++14	100 / 100	1517 ms	394056 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std ;

#define ff      first
#define ss      second

typedef long double       ll ;
typedef pair<ll,ll>   pll ;

const int M = 1e6+2 ;
const int N = 1e5+2 ;

int mxCoor[ M ] ;
vector <pll> points ;
int sz ;
pll dp [N];
ll Lowpend, Hgpend, Midpend ;
ll last ;

struct info {
    ll m, b, ind ;
    info ( ll m1, ll b1, ll ind1 ) {
        m = m1 ;
        b = b1 ;
        ind = ind1 ;
    }
};

vector <info> convex ;

ll comm ( info A, info B ) {
    return (1.0*B.b - A.b) / (A.m - B.m) ;
}

void add ( info cur ) {
    while ( 1 ) {
        if ( convex.size() < 2 ) {
            convex.push_back ( cur ) ;
            break ;
        }
        info tp = convex.back() ;
        convex.pop_back() ;
        info scn = convex.back() ;
        if ( comm ( cur, scn ) > comm ( scn, tp ) ) {
            convex.push_back ( tp ) ;
            convex.push_back ( cur ) ;
            break ;
        }
    }
}

info query ( int p ) {
    int lw = 0, hg = convex.size() ;
    --hg ;
    while ( lw < hg ) {
        int mid = (lw+hg)/2 ;
        long double inter = comm(convex[mid], convex[mid+1]) ;
    //    cout << mid << ' ' << inter << ' '<< p << '\n' ;
        if ( inter == p ) return convex[mid] ;
        if ( inter < p ) lw = mid+1 ;
        else hg = mid ;
    }
    return convex[lw] ;
}

ll intersect ( int k ) {
    ll inters = points[k].ss - points[k+1].ff + 1;
    if ( inters < 0 ) inters = 0 ;
    inters *= inters ;
    return inters ;
}

long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
    memset ( mxCoor, -1, sizeof mxCoor ) ;
    for ( int i = 0 ; i < n ; ++i ) {
        if ( c[i] >= r[i] ) mxCoor [r[i]] = max ( mxCoor [r[i]], c[i] ) ;
        else mxCoor [c[i]] = max ( mxCoor [c[i]], r[i] ) ;
    }

    int mx = -1 ;
    for ( int i = 0 ; i < m ; ++i ) {
        if ( mxCoor[i] <= mx ) continue ;
        mx = mxCoor[i] ;
        points.push_back({i,mx}) ;
    }

    sz = points.size() ;
    last = mx+1 ;
    Lowpend = 0, Hgpend = 1ll*last*last ;
    ll ans = 0 ;
    k = min(k,sz) ;

    while ( fabs(Lowpend-Hgpend) > 1e-6 ) {
        convex.clear() ;
        Midpend = (Lowpend+Hgpend)/2 ;
        dp[sz] = {0,0} ;
        info *x = new info( 1ll*points[sz-1].ss, points[sz-1].ss * points[sz-1].ss, 1ll*sz ) ;
        add(*x) ;
        for ( int i = sz-1 ; i >= 0 ; --i ) {
            info opt = query(-2*(points[i].ff-1)) ;
            dp[i].ff = (points[i].ff-1)*(points[i].ff-1) - 2*(points[i].ff-1)*(opt.m) + opt.b + Midpend;
            dp[i].ss = dp[(int)opt.ind].ss + 1 ;
            if ( i ) {
                info *x = new info( 1ll*points[i-1].ss, 1ll*dp[i].ff - intersect (i-1) + points[i-1].ss * points[i-1].ss, 1ll*i ) ;
                add(*x) ;
            }
        }
      //  cout << dp[0].ff << ' ' << dp[0].ss << ' ' << Midpend << '\n' ;
        if ( dp[0].ss >= k ) Lowpend = Midpend, ans = dp[0].ff - (long long)(k * Midpend)  ;
        else Hgpend = Midpend ;
    }
  //  cout << Hgpend << '\n' ;
    return (long long)ans;
}

/*
10 100 3
0 0
1 1
2 2
3 3
4 4
5 5
6 6
50 50
81 81
99 99
*/

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