제출 #32079

#제출 시각아이디문제언어결과실행 시간메모리
32079osmanorhanAliens (IOI16_aliens)C++14
0 / 100
0 ms9836 KiB
#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, h-1 ); now += h; } 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; }

컴파일 시 표준 에러 (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++)
                      ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...