Submission #718055

#TimeUsernameProblemLanguageResultExecution timeMemory
718055vinnipuh01Group Photo (JOI21_ho_t3)C++17
100 / 100
3241 ms67720 KiB
#include <iostream> #include <bits/stdc++.h> #include <cmath> #include <algorithm> #include <vector> #include <deque> #include <set> #include <stack> #include <string> #include <map> #include <queue> //#define int long long #define sqrt sqrtl using namespace std; const long long oo = 1e9; long long sum, ans = 0, mx = 0, mn = 1000000000, num, pos; /* ViHHiPuh (( `'-""``""-'` )) )-__-_.._-__-( / --- (o _ o) --- \ \ .-* ( .0. ) *-. / _'-. ,_ '=' _, .-'_ / `;#'#'# - #'#'#;` \ \_)) -----'#'----- ((_/ # --------- # '# ------- ------ #' /..-'# ------- #'-.\ _\...-\'# -- #'/-.../_ ((____)- '#' -(____)) cout << fixed << setprecision(6) << x; freopen ( "sum.in", "r", stdin ) */ int n, a[ 5001 ], t[ 20001 ], tt[ 20001 ], b[ 5001 ]; int dp[ 5002 ], d[ 5002 ][ 5002 ]; void build( int v, int tl, int tr ) { if ( tl == tr ) { t[ v ] = 1; return; } int mid = ( tl + tr ) / 2; build( v + v, tl, mid ); build( v + v + 1, mid + 1, tr ); t[ v ] = t[ v + v ] + t[ v + v + 1 ]; } void build1( int v, int tl, int tr ) { tt[ v ] = 0; if ( tl == tr ) { return; } int mid = ( tl + tr ) / 2; build1( v + v, tl, mid ); build1( v + v + 1, mid + 1, tr ); } void upd( int v, int tl, int tr, int pos ) { if ( tl > pos || tr < pos ) return; if ( tl == tr ) { t[ v ] = 0; tt[ v ] = 1; return; } int mid = ( tl + tr ) / 2; upd( v + v, tl, mid, pos ); upd( v + v + 1, mid + 1, tr, pos ); t[ v ] = t[ v + v ] + t[ v + v + 1 ]; tt[ v ] = tt[ v + v ] + tt[ v + v + 1 ]; } void gett( int v, int tl, int tr, int pos ) { if ( tl > pos ) { sum += tt[ v ]; return; } if ( tr < pos ) { num += t[ v ]; return; } if ( tl == tr ) { return; } int mid = ( tl + tr ) / 2; gett( v + v, tl, mid, pos ); gett( v + v + 1, mid + 1, tr, pos ); } main () { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; for ( int i = 1; i <= n; i ++ ) { cin >> a[ i ]; b[ a[ i ] ] = i; dp[ i ] = oo; } build( 1, 1, n ); for ( int i = 1; i <= n; i ++ ) { build1( 1, 1, n ); for ( int j = i; j >= 1; j -- ) { d[ j ][ i ] = d[ j + 1 ][ i ]; upd( 1, 1, n, b[ j ] ); num = sum = 0; gett( 1, 1, n, b[ j ] ); d[ j ][ i ] += num; d[ j ][ i ] += sum; // cout << j << " " << i << " - " << d[ j ][ i ] << "\n"; } } for ( int i = 1; i <= n; i ++ ) { for ( int j = i - 1; j >= 0; j -- ) { dp[ i ] = min( dp[ i ], dp[ j ] + d[ j + 1 ][ i ] ); } } cout << dp[ n ]; } /* h[ i ] + i * 2 < h[ i + 1 ] + i * 2 + 4 h[ i ] - h[ i + 1 ] < 4 3 5 2 4 1 5 9 8 14 13 */

Compilation message (stderr)

Main.cpp:102:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  102 | main () {
      | ^~~~
#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...