Submission #32078

#	Time	Username	Problem	Language	Result	Execution time	Memory
32078		osmanorhan	Aliens (IOI16_aliens)	C++14	60 / 100	2000 ms	356440 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;

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

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

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

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 = sq(v[i].se-v[m].fi+1) - dp[m] + 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 );
}

long long take_photos(int N, int m, int k, vector<int> r, vector<int> c) {
    n = N;
    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;
    //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;

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

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

    n = v.size();

    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 );
        //for(int i=0;i<n;i++) printf("%d ",dn[i][j]); printf(" ---- j=%d\n",j);
    }

    return dn[0][k];
}

Compilation message (stderr)

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

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