Submission #913894

#	Time	Username	Problem	Language	Result	Execution time	Memory
913894		andrei_iorgulescu	Group Photo (JOI21_ho_t3)	C++14	100 / 100	444 ms	97584 KiB

Main

#include <bits/stdc++.h>

using namespace std;

int inf = 1e9;

int n,a[5005],pos[5005];
int dp[5005],cost[5005][5005];
int v[5005],sp[5005];
int aib[5005];

void update(int pos,int val)
{
    for (int i = pos; i <= n; i += (i & -i))
        aib[i] += val;
}

int query(int pos)
{
    int r = 0;
    for (int i = pos; i > 0; i -= (i & -i))
        r += aib[i];
    return r;
}

void prec_cost()
{
    for (int j = 1; j <= n; j++)
    {
        ///aici calculez cost[i][j]
        for (int i = 1; i <= n; i++)
            aib[i] = 0,v[i] = 0;
        for (int i = 1; i <= n; i++)
            if (a[i] > j)
                v[i] = 1;
        for (int i = 1; i <= n; i++)
            sp[i] = sp[i - 1] + v[i];
        int cst = 0;
        for (int i = j; i >= 1; i--)
        {
            ///in primul rand cate neinversiuni sunt intre astea <=> (j - i) - cate de pana acum sunt pe poz mai mici
            cst += (j - i) - query(pos[i] - 1);
            ///in al doilea rand cate mai mari ca j sunt in spate
            cst += sp[pos[i] - 1];
            cost[i][j] = cst;
            update(pos[i],1);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i],pos[a[i]] = i;
    prec_cost();
    dp[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        dp[i] = inf;
        for (int j = 0; j < i; j++)
            dp[i] = min(dp[i],dp[j] + cost[j + 1][i]);
    }
    cout << dp[n];
    return 0;
}

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