Submission #869942

#	Time	Username	Problem	Language	Result	Execution time	Memory
869942		boris_mihov	Group Photo (JOI21_ho_t3)	C++17	0 / 100	1 ms	348 KiB

Main

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
 
typedef long long llong;
const int MAXN = 5000 + 10;
const int INF  = 1e9;
 
int n;
int a[MAXN];
int dp[MAXN];
int pos[MAXN];
 
struct Fenwick
{
    int tree[MAXN];
    void update(int pos, int value)
    {
        for (int idx = pos ; idx <= n ; idx += idx & (-idx))
        {
            tree[idx] += value;
        }
    }
    
    int query(int pos)
    {
        int res = 0;
        for (int idx = pos ; idx >= 1 ; idx -= idx & (-idx))
        {
            res += tree[idx];
        }
    
        return res;
    }
};

Fenwick treePos;
Fenwick treeSmaller;
void solve()
{
    dp[n + 1] = 0;
    for (int from = n ; from >= 1 ; --from)
    {
        treePos.update(pos[from], 1);
        dp[from] = INF;
        int add = 0;
 
        for (int next = from ; next <= n ; ++next)
        {
            treeSmaller.update(pos[next], 1);
            add += treePos.query(pos[next]) - 1;
            add -= treeSmaller.query(n) - treeSmaller.query(pos[next]);
            dp[from] = std::min(dp[from], dp[next + 1] + add);
        }
    }
 
    std::cout << dp[1] << '\n';
}
 
void input()
{
    std::cin >> n;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> a[i];
        pos[a[i]] = i;
    }
}
 
void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}
 
int main()
{
    fastIOI();
    input();
    solve();
 
    return 0;
}

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