oj.uz

답안 #258400

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
258400 2020-08-05T21:51:29 Z Kubin 휴가 (IOI14_holiday) C++17
100 / 100
 899 ms 9308 KB 
#include <bits/stdc++.h>

using namespace std;

template<typename T>
struct fenwick_tree
{
    size_t n;
    vector<T> F;

    static constexpr size_t lsb(size_t x) { return x & -x; }

    fenwick_tree(size_t m) : n(m), F(n+1) {}

    T get_prefix(size_t p) const
    {
        T r = 0;
        while(p)
            r += F[p], p -= lsb(p);
        return r;
    }

    void delta(size_t p, T v)
    {
        p++;
        while(p <= n)
            F[p] += v, p += lsb(p);
    }

    size_t lower_bound(T v)
    {
        if(v == 0) return 0;
        size_t p = 0; T s = 0;
        for(size_t k = __lg(n) + 1; k --> 0; )
            if(p + (1 << k) <= n and s + F[p + (1 << k)] < v)
                s += F[p += (1 << k)];
        return p + 1;
    }
};

struct max_sum_set
{
    vector<int> A;
    vector<size_t> B;
    fenwick_tree<int> cnt;
    fenwick_tree<int64_t> sum;

    max_sum_set(vector<int> a) : A(a), B(A.size()), cnt(A.size()), sum(A.size())
    {
        auto C = B;
        iota(C.begin(), C.end(), 0);
        sort(C.begin(), C.end(), [&](size_t lhs, size_t rhs) {
            return A[lhs] > A[rhs];
        });
        for(size_t i = 0; i < A.size(); i++)
            B[C[i]] = i;
    }

    void push(size_t i)
    {
        if(i >= A.size()) return;
        cnt.delta(B[i], +1);
        sum.delta(B[i], +A[i]);
    }

    void pop(size_t i)
    {
        if(i >= A.size()) return;
        cnt.delta(B[i], -1);
        sum.delta(B[i], -A[i]);
    }

    int64_t get(size_t k)
    {
        return sum.get_prefix(cnt.lower_bound(min(k, (size_t)cnt.get_prefix(A.size()))));
    }
};

void divida_et_impera(
    size_t d1, size_t d2, size_t p1, size_t p2,
    vector<int64_t>& result, max_sum_set& V, const vector<int>& A, int mv)
{
    if(d1 >= d2)
        return;

    size_t d = (d1 + d2) / 2, p = p1;
    int64_t& r = result[d];

    for(size_t i = p1; i < p2 and mv*i <= d; i++)
    {
        auto v = V.get(d-mv*i);
        if(v > r)
            r = v, p = i;
        V.push(i);
    }
    for(size_t i = p1; i < p2 and mv*i <= d; i++)
        V.pop(i);

    divida_et_impera(d1, d, p1, p+1, result, V, A, mv);
    for(size_t i = p1; i < p; i++) V.push(i);
    divida_et_impera(d+1, d2, p, p2, result, V, A, mv);
    for(size_t i = p1; i < p; i++) V.pop(i);
}

vector<int64_t> best_values(vector<int> A, size_t d, int mv = 1)
{
    vector<int64_t> result(d+1);
    max_sum_set V(A);
    divida_et_impera(0, d+1, 0, A.size()+1, result, V, A, mv);
    return result;
}

int64_t solve_right(const vector<int>& A, size_t s, size_t d)
{
    auto R = best_values(vector<int>(A.begin() + s, A.end()), d),
         L = best_values(vector<int>(A.rbegin() + (A.size()-s), A.rend()), d, 2);
    int64_t result = 0;
    for(size_t r = 0; r <= d; r++)
        result = max(result, R[r] + L[d-r]);
    return result;
}

long long int findMaxAttraction(int n, int start, int d, int a[])
{
    vector<int> A(a, a + n);
    int64_t result = solve_right(A, start, d+1);
    reverse(A.begin(), A.end());
    result = max(result, solve_right(A, n-1 - start, d+1));
    return result;
}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 752 ms 8288 KB Output is correct
2 Correct 544 ms 8488 KB Output is correct
3 Correct 744 ms 8492 KB Output is correct
4 Correct 593 ms 8544 KB Output is correct
5 Correct 693 ms 7020 KB Output is correct
6 Correct 251 ms 4596 KB Output is correct
7 Correct 394 ms 4408 KB Output is correct
8 Correct 422 ms 4688 KB Output is correct
9 Correct 193 ms 5020 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 640 KB Output is correct
2 Correct 13 ms 640 KB Output is correct
3 Correct 18 ms 640 KB Output is correct
4 Correct 12 ms 512 KB Output is correct
5 Correct 10 ms 512 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct

Subtask #4
53.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 767 ms 8952 KB Output is correct
2 Correct 899 ms 9308 KB Output is correct
3 Correct 91 ms 2324 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 543 ms 4884 KB Output is correct
9 Correct 553 ms 5032 KB Output is correct