Submission #200272

#	Time	Username	Problem	Language	Result	Execution time	Memory
200272		oscarsierra12	Aliens (IOI16_aliens)	C++14	60 / 100	2078 ms	10220 KiB

aliens

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

typedef pair<int,int>   pii ;
typedef long long       ll ;

const int M = 1e6+2 ;
const int N = 1e5+2 ;
const ll inf = 1e15 ;

int mxCoor[ M ] ;
vector <pii> points ;
int sz ;
ll dp [N][3];
int ac ;

void solve ( int l, int r, int optl, int optr ) {
    if ( l > r ) return ;
    int mid = (l+r)>>1 ;
    dp[mid][ac%2] = inf ;
    int optimal = 0 ;
    for ( int k = optl ; k < min (optr+1, mid) ; ++k ) {
        ll inters = points[k].second - points[k+1].first + 1;
        if ( inters < 0 ) inters = 0 ;
        inters *= inters ;
//        cout << k << " to " << k+1 << ' ' << inters << ' ' << points[k].second << ' ' << points[k+1].first << '\n' ;
        ll cost = points[mid].second - points[k+1].first + 1;
        cost *= cost;
        cost -= inters ;
//        cout << dp[k][(ac-1)%2] << ' ' << cost << ' ' << dp[mid][ac%2] << endl ;
        if ( dp[k][(ac-1)%2] + cost < dp[mid][ac%2] ) {
            dp[mid][ac%2] = dp[k][(ac-1)%2] + cost ;
            optimal = k ;
        }
    }
    solve ( l, mid-1, optl, optimal ) ;
    solve ( mid+1, r, optimal, optr ) ;
}

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 ;
    points.push_back({-1,-1}) ;
    for ( int i = 0 ; i < m ; ++i ) {
        if ( mxCoor[i] <= mx ) continue ;
        mx = mxCoor[i] ;
        points.push_back({i,mx}) ;
    }
    sz = points.size() ;
    for ( int i = 1 ; i < sz ; ++i ) dp[i][0] = inf ;

    for ( int i = 1 ; i <= k ; ++i ) {
        ac = i ;
        solve ( 1, sz-1, 0, sz-1 ) ;
    }
    return dp[sz-1][k%2];
}

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