oj.uz

Submission #869942

# Submission time Handle Problem Language Result Execution time Memory
869942 2023-11-06T11:54:10 Z boris_mihov Group Photo (JOI21_ho_t3) C++17
0 / 100
 1 ms 348 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -