oj.uz

Submission #163336

# Submission time Handle Problem Language Result Execution time Memory
163336 2019-11-12T17:28:02 Z Trans Studentsko (COCI14_studentsko) C++14
10 / 100
 23 ms 9976 KB 
#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.0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 2424 KB Output isn't correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 1016 KB Output isn't correct

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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