Submission #163336

#	Time	Username	Problem	Language	Result	Execution time	Memory
163336		Trans	Studentsko (COCI14_studentsko)	C++14	10 / 100	23 ms	9976 KiB

studentsko

#include <bits/stdc++.h>

using namespace std;

#define pb push_back

const int maxn = 5e3 + 5;

map<int, int> pos;
int a[maxn], b[maxn];
int n, m, cnt;
vector<int> has[maxn];
int check[maxn][maxn];

int main() {
    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        cin >> a[i];
        b[i] = a[i];
    }

    sort(a, a + n);

    for (int i = 0; i < n; i++) {
        pos[a[i]] = cnt;
        if ((i + 1) % m == 0) cnt++;
    }

    for (int i = 0; i < cnt; i++) {
        sort(has[i].begin(), has[i].end());
    }

    for (int i = 0; i < n; i++) {
        a[i] = pos[b[i]];
        has[a[i]].pb(i);
    }

    for (int i = 0; i < cnt; i++) {
        check[i][i] = 1;
        int pre = has[i][m - 1];
        for (int j = i + 1; j < cnt; j++) {
            if (has[j][0] > pre) {
                check[i][j] = 1;
                pre = has[j][m - 1];
            } else {
                break;
            }
        }
    }

    int ans = 1e9;
    for (int i = cnt - 1; i >= 0; i--) {
        int L = 0;
        int R = n - 1;
        for (int j = cnt - 1; j >= i; j--) {
            while (L < n && a[L] > j) {
                L++;
            }
            while (R >= 0 && a[R] < i) {
                R--;
            }
            if (check[i][j]) {
//                cout << i << ' ' << j << endl;
                int res = 0;
                if (a[L] == i - 1) {
                    int cur = L;
                    int rem = m;
                    while (cur < n) {
                        if (a[cur] <= j && a[cur] != i - 1) {
                            break;
                        }
                        if (a[cur] == i - 1) rem--;
                        cur++;
                    }
                    res += (i - 1) * m + rem;
                } else {
                    res += i * m;
                }
                if (a[R] == j + 1) {
                    int cur = R;
                    int rem = m;
                    while (cur >= 0) {
                        if (a[cur] >= i && a[cur] != j + 1) {
                            break;
                        }
                        if (a[cur] == j + 1) rem--;
                        cur--;
                    }
                    res += (cnt - j - 2) * m + rem;
                } else {
                    res += (cnt - j - 1) * m;
                }
//                cout << res << endl;
                ans = min(ans, res);
            } else {
                continue;
            }
        }
    }

    cout << ans;

    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10