oj.uz

Submission #797345

# Submission time Handle Problem Language Result Execution time Memory
797345 2023-07-29T09:47:54 Z finn__ Diversity (CEOI21_diversity) C++17
0 / 100
 1 ms 468 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,sse4")

#include <bits/stdc++.h>
using namespace std;

constexpr size_t N = 300000, M = 300000;

uint64_t f[2][N], s[M], p[M];

template <typename T>
T gauss(T n) { return (n * (n + 1)) / 2; }

template <typename T>
T range_gauss(T a, T b)
{
    return gauss(b) - (a ? gauss(a - 1) : 0);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    size_t n, q;
    cin >> n >> q;
    size_t m;
    for (size_t i = 0; i < n; ++i)
    {
        size_t a;
        cin >> a;
        s[a - 1]++;
        m = max(m, a - 1);
    }

    sort(s, s + m);
    partial_sum(s, s + m, p);
    memset(f, 255, sizeof f);
    f[0][0] = 0;

    for (size_t j = 0; j < m; ++j)
    {
        size_t const u = j & 1, v = (j & 1) ^ 1;
        memset(f[v], 255, sizeof f[v]);
        for (size_t i = 0; i <= (j ? p[j - 1] : 0); ++i)
            if (f[u][i] != UINT64_MAX)
            {
                // Extend left
                uint64_t l = i, r = l + s[j] - 1;
                f[v][i + s[j]] = min(f[v][i + s[j]], f[u][i] + (r + 1) * n - l * l - range_gauss(l, r));

                // Extend right
                r = n - ((j ? p[j - 1] : 0) - i) - 1, l = r - s[j] + 1;
                f[v][i] = min(f[v][i], f[u][i] + (r + 1) * n - l * l - range_gauss(l, r));
            }
    }

    uint64_t ans = UINT64_MAX;
    for (size_t i = 0; i < n; ++i)
        ans = min(ans, f[m & 1][i]);
    cout << ans << '\n';
}

Compilation message

diversity.cpp: In function 'int main()':
diversity.cpp:41:26: warning: 'm' may be used uninitialized in this function [-Wmaybe-uninitialized]
   41 |     for (size_t j = 0; j < m; ++j)
      |                        ~~^~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 400 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 400 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 36.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 400 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -