Submission #373479

#	Time	Username	Problem	Language	Result	Execution time	Memory
373479		vaaven	Group Photo (JOI21_ho_t3)	C++14	100 / 100	733 ms	118652 KiB

Main

#pragma GCC optimize("O3")
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#include <stack>
#include <iomanip>
#include <bitset>
#include <map>
#include <cassert>
#include <array>
#include <queue>
#include <cstring>
#include <random>
#include <unordered_set>
#include <unordered_map>
#define pqueue priority_queue
#define pb(x) push_back(x)
// #define endl '\n'
#define all(x) x.begin(), x.end()
 #define int long  long
      
using namespace std;
      
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
// typedef tuple<ll, ll, ll> tiii;
typedef pair<int, int> pii;
typedef vector<pair<int, int> > vpii;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<char> vc;
      
const int inf = 1e9 + 228;
const ll infll = 1e18;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ld eps = 1e-14;
      
      
void fast_io(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
//    cout.tie(0);
//    freopen("d.in", "r", stdin);
//    freopen("d.out", "w", stdout);
}

const int maxn = 5e3 + 228;
int t[maxn];

void add(int i, int x){
    i++;
    for(; i<maxn; i+=i&-i)
        t[i] += x;
}

int get(int i){
    i++;
    int res = 0;
    for(; i>0; i-=i&-i)
        res += t[i];
    return res;
}

int dp[maxn][maxn];
int dp2[maxn];

void solve(){
    int n;
    cin >> n;
    vi a(n);
    for(int &i:a)
        cin >> i;
    for(int i=1; i<=n; i++){
        vi nw;
        for(int j:a){
            if(j != i-1)
                nw.pb(j);
        }
        a = nw;
        vi pos(n+1, 0);
        for(int j=0; j<a.size(); j++){
            pos[a[j]] = j;
        }
        for(int &j:t)
            j = 0;
        for(int j=i; j<=n; j++){
            dp[i][j] = dp[i][j-1] + pos[j] - (get(maxn-2) - get(pos[j]));
            add(pos[j], 1);
        }
    }
    for(int i=1; i<=n; i++){
        dp2[i] = inf;
        for(int j=0; j<i; j++){
            dp2[i] = min(dp2[i], dp2[j] + dp[j+1][i]);
        }
    }
    cout << dp2[n] << endl;
}

signed main(){
    fast_io();
//    srand(time(NULL));
    cout << fixed << setprecision(10);
    int q = 1;
//    cin >> q;
    while(q--)
        solve();
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:87:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |         for(int j=0; j<a.size(); j++){
      |                      ~^~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 32 / 32
• Subtask 4: 20 / 20
• Subtask 5: 36 / 36