Submission #666739

#	Time	Username	Problem	Language	Result	Execution time	Memory
666739		Astrayt	Group Photo (JOI21_ho_t3)	C++17	100 / 100	360 ms	628 KiB

Main

//君の手を握ってしまったら
//孤独を知らないこの街には
//もう二度と帰ってくることはできないのでしょう
//君が手を差し伸べた 光で影が生まれる
//歌って聞かせて この話の続き
//連れて行って見たことない星まで
//さユリ - 花の塔
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define starburst ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define pii pair<int,int>
#define pb push_back
#define ff first
#define ss second
#define mp make_pair
#define maxn 5005
#define mod 1000000007

struct FenwickTree{
    int val[maxn];
    void init(){
        for(auto &x:val) x = 0;
    }
    void modify(int p, int x){
        for(; p < maxn; p += (p & -p)) val[p] += x;
    }
    int query(int p){
        int ret = 0;
        for(; p; p -= (p & -p)) ret += val[p];
        return ret;
    }
}bit;

void solve(){
    int n; cin >> n;
    vector<int> v(n + 1, 0), pos(n + 1, 0), dp(n + 1, 1e18);
    for(int i = 1; i <= n; ++i){
        cin >> v[i];
        pos[v[i]] = i;  
    }
    dp[0] = 0;
    bit.init();
    for(int i = 1; i <= n; ++i){
        FenwickTree tmp;
        tmp.init();
        bit.modify(pos[i], 1);
        int cur = 0;
        for(int j = i; j >= 1; --j){
            cur = cur - tmp.query(pos[j]) + (i - bit.query(pos[j]));
            tmp.modify(pos[j], 1);
            dp[i] = min(dp[j - 1] + cur, dp[i]);
        }
    }
    cout << dp[n] << '\n';
}

signed main(){
    starburst
    int t = 1; //cin >> t;
    while(t--) solve();
}

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