#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 );
now += h;
}
assert( loc[k-1].se == n );
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
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++)
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
9840 KB |
Execution killed because of forbidden syscall gettid (186) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
9840 KB |
Execution killed because of forbidden syscall gettid (186) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
9840 KB |
Execution killed because of forbidden syscall gettid (186) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
9840 KB |
Execution killed because of forbidden syscall gettid (186) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
9840 KB |
Execution killed because of forbidden syscall gettid (186) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
9840 KB |
Execution killed because of forbidden syscall gettid (186) |
| 2 |
Halted |
0 ms |
0 KB |
- |
