Submission #32081

#	Time	Username	Problem	Language	Result	Execution time	Memory
32081		osmanorhan	Aliens (IOI16_aliens)	C++14	4 / 100	0 ms	9836 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define all( x ) x.begin(), x.end()
#define umin( x, y ) x = min( x, (y) )
#define umax( x, y ) x = max( x, (y) )

using namespace std;

typedef long long Lint;
typedef pair<int,int> ii;

const int maxn = 1000020;

bool comp( const ii &a, const ii &b ) {
    return a.se < b.se;
}

Lint sq( Lint x ) { return x*x; }

int n, K;
vector< vector<Lint> > dn;
vector<Lint> dp;
vector<ii> v, v2;

Lint calc( int l, int r ) {
    if( l > r ) return 0;
    if( r >= n || l < 0 ) return 1e18;
    return sq( v[r].se-v[l].fi+1 ) - dp[l];
}

void f( int l, int r, int optl, int optr, int n ) {
    if( l > r ) return;
    int m = (l+r)/2;
    int optm = m;
    Lint mini = 1e18;

    for(int i=max(m,optl);i<=optr;i++) {
        Lint val = calc( m, l ) + dn[i+1][n-1];
        if( mini > val ) {
            mini = val;
            optm = i;
        }
    }
    dn[m][n] = mini;
    f( l, m-1, optl, optm, n );
    f( m+1, r, optm, optr, n );
}

ii loc[maxn];

inline Lint val( int i ) {
    return calc( loc[i].fi, loc[i].se );
}

bool check( int i ) {
    if( i < 0 || i > K-2 ) return 0;
    Lint now = val( i ) + val( i+1 );
    bool c = 0;
    while( calc( loc[i].fi, loc[i].se+1 ) + calc( loc[i+1].fi+1, loc[i+1].se ) < now ) c = 1, loc[i].se++, loc[i+1].fi++, now = val( i ) + val( i+1 );
    while( calc( loc[i].fi, loc[i].se-1 ) + calc( loc[i+1].fi-1, loc[i+1].se ) < now ) c = 1, loc[i].se--, loc[i+1].fi--, now = val( i ) + val( i+1 );
    if( c ) {
        check( i-1 );
        check( i+1 );
        return 1;
    }
    return 0;
}

long long take_photos(int N, int m, int k, vector<int> r, vector<int> c) {
    n = N;
    K = k;
    for(int i=0;i<r.size();i++) {
        if( r[i] > c[i] ) swap( r[i], c[i] );
        v.pb( ii( r[i], c[i] ) );
    }
    sort( all( v ), comp );

    for(int i=0;i<v.size();i++) {
        while( v2.size() && v2[v2.size()-1].fi >= v[i].fi ) v2.pop_back();
        v2.pb( v[i] );
    }
    v = v2;

    n = v.size();
    //for(int i=0;i<v.size();i++)
        //printf("-- %d %d\n",v[i].fi,v[i].se);
    dp.resize(v.size());
    for(int i=0;i<dp.size();i++)
        dp[i] = i? sq( max( 0, v[i-1].se-v[i].fi+1 ) ):0;

    if( k*k < n && 0 ) {

        dn.resize(v.size()+1);

        for(int i=0;i<dn.size();i++)
            dn[i].resize( k+1 );

        for(int i=0;i<=k-1;i++) dn[n][i] = 0;
        for(int i=0;i<n;i++) dn[i][0] = 1e18;
        //printf("asd\n");
        for(int j=1;j<=k;j++) {
            f( 0, n-1, 0, n-1, j );
        }
        return dn[0][k];
    }

    for(int i=0,now=0;i<k;i++) {
        int h = (n-now)/(k-i);
        loc[i] = ii( now, now+h-1 );
        //printf("asd %d %d %d --- %d %d\n",n,now,h,loc[i].fi,loc[i].se);
        now += h;
    }

  	assert( loc[k-1].se == n-1 );
    bool flag = true;
    while( flag ) {
        int c = 0;
        for(int i=0;i<k-1;i++)
            if( check( i ) ) c = 1;
        if( !c ) flag = false;
    }
    Lint ans = 0;
    for(int i=0;i<k;i++)
        ans += val( i );
    return ans;
}

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:75:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<r.size();i++) {
                  ^
aliens.cpp:81:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v.size();i++) {
                  ^
aliens.cpp:91:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<dp.size();i++)
                  ^
aliens.cpp:98:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<dn.size();i++)
                      ^

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