oj.uz

Submission #894027

# Submission time Handle Problem Language Result Execution time Memory
894027 2023-12-27T20:09:07 Z n3rm1n Studentsko (COCI14_studentsko) C++17
100 / 100
 3 ms 780 KB 
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int MAXN = 5005;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
int n, k, a[MAXN], x[MAXN];
unordered_map < int, int > mp;
void read()
{
    cin >> n >> k;
    for (int i = 1; i <= n; ++ i)
    {
        cin >> a[i];
        x[i] = a[i];
    }
    sort(x+1, x+n+1);
    int group = 1;
    for (int i = 1; i <= n; ++ i)
    {

        mp[x[i]] = group;
        if(i % k == 0)group ++;
    }
}
int b[MAXN];
int dp[MAXN];
void count_inversions()
{
    for (int i = 1; i <= n; ++ i)
    {
        b[i] = mp[a[i]];
       /// cout << b[i] << " ";
    }
    /// cout << endl;

    memset(dp, -1, sizeof(dp));
    dp[0] = 0;
    int maxlen = 0;
    for (int i = 1; i <= n; ++ i)
    {
        if(b[i] >= dp[maxlen])
        {
            maxlen ++;
            dp[maxlen] = b[i];
        }
        else
        {
            for (int j = maxlen-1; j >= 0; -- j)
                if(dp[j] <= b[i])dp[j+1] = min(dp[j+1], b[i]);
        }
    }

    cout << n - maxlen << endl;
}
int main()
{
    speed();

    read();
    count_inversions();
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 616 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 2 ms 604 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 2 ms 604 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 3 ms 604 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 604 KB Output is correct
2 Correct 2 ms 780 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 608 KB Output is correct
2 Correct 2 ms 604 KB Output is correct