#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;
optl = 0;
optr = n-1;
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 ) );
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 );
}
return dn[0][k];
}
Compilation message
aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:47:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<r.size();i++) {
^
aliens.cpp:53:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<v.size();i++) {
^
aliens.cpp:62:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<dp.size();i++)
^
aliens.cpp:67:18: 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 |
Correct |
0 ms |
2024 KB |
Correct answer: answer = 4 |
| 2 |
Runtime error |
0 ms |
2024 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2024 KB |
Correct answer: answer = 1 |
| 2 |
Incorrect |
0 ms |
2024 KB |
Wrong answer: output = 1000000000000000000, expected = 4 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2024 KB |
Correct answer: answer = 4 |
| 2 |
Runtime error |
0 ms |
2024 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2024 KB |
Correct answer: answer = 4 |
| 2 |
Runtime error |
0 ms |
2024 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2024 KB |
Correct answer: answer = 4 |
| 2 |
Runtime error |
0 ms |
2024 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2024 KB |
Correct answer: answer = 4 |
| 2 |
Runtime error |
0 ms |
2024 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
