oj.uz

답안 #105058

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
105058 2019-04-10T11:27:05 Z alexpetrescu 휴가 (IOI14_holiday) C++14
100 / 100
 1609 ms 15732 KB 
#include"holiday.h"
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>

#define vec std::vector
#define myc std::pair < int, int >
#define x first
#define y second

#define ll long long

#define MAXN 100000
#define MAXP 265000

struct node {
    int cnt;
    ll sum;
} aint[MAXP];
ll val;
int poz, cnt;

void update(int p, int st, int dr) {
    if (st == dr) {
        aint[p].cnt = val > 0;
        aint[p].sum = val;
    } else {
        int m = (st + dr) / 2;
        if (poz <= m) update(2 * p, st, m);
        else update(2 * p + 1, m + 1, dr);
        aint[p].cnt = aint[2 * p].cnt + aint[2 * p + 1].cnt;
        aint[p].sum = aint[2 * p].sum + aint[2 * p + 1].sum;
    }
}

void query(int p, int st, int dr) {
    if (poz != dr + 1)
        return ;
    if (aint[p].cnt <= cnt) {
        cnt -= aint[p].cnt;
        val += aint[p].sum;
        poz = st;
        return ;
    }
    if (st == dr)
        return ;
    int m = (st + dr) / 2;
    query(2 * p + 1, m + 1, dr);
    query(2 * p, st, m);
}

void divide(int cost, vec < myc > &V, vec < ll > &dp, int left, int right, int st, int dr, int &unde) {
    if (left > right)
        return ;
    while (unde < st) {
        unde++;
        poz = V[unde].y;
        val = V[unde].x;
        update(1, 0, V.size() - 1);
    }
    while (unde > st) {
        poz = V[unde].y;
        val = 0;
        update(1, 0, V.size() - 1);
        unde--;
    }
    int sol = st, m = (left + right) / 2;
    poz = V.size();
    val = 0;
    cnt = m - cost * st - cost;
    query(1, 0, V.size() - 1);
    dp[m] = val;
    for (int i = st + 1; i <= dr; i++) {
        unde++;
        poz = V[unde].y;
        val = V[unde].x;
        update(1, 0, V.size() - 1);

        poz = V.size();
        val = 0;
        cnt = m - cost * i - cost;
        query(1, 0, V.size() - 1);
        if (val > dp[m]) {
            sol = i;
            dp[m] = val;
        }
    }
    divide(cost, V, dp, left, m - 1, st, sol, unde);
    divide(cost, V, dp, m + 1, right, sol, dr, unde);
}

inline void solve(int cost, vec < ll > &dp, vec < int > &v) {
    if (v.empty())
        return ;
    memset(aint, 0, sizeof aint);
    vec < myc > W(v.size()), V(v.size());
    for (int i = 0; i < (int)v.size(); i++)
        W[i] = {v[i], i};
    std::sort(W.begin(), W.end());
    for (int i = 0; i < (int)V.size(); i++)
        V[W[i].y] = {W[i].x, i};
    int unde = -1;
    divide(cost, V, dp, 0, dp.size() - 1, 0, v.size() - 1, unde);
}

long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
    vec < ll > left1(d + 1, 0), left2(d + 1, 0), right1(d + 1, 0), right2(d + 1, 0);
    vec < int > st, dr;
    for (int i = start - 1; i >= 0; i--)
        st.push_back(attraction[i]);
    for (int i = start + 1; i < n; i++)
        dr.push_back(attraction[i]);
    solve(1, left1, st);
    solve(2, left2, st);
    solve(1, right1, dr);
    solve(2, right2, dr);

    ll ans = 0;
    for (int i = 0; i <= d; i++)
        ans = std::max(ans, std::max(left2[i] + right1[d - i], right2[i] + left1[d - i]));
    for (int i = 0; i < d; i++)
        ans = std::max(ans, attraction[start] + std::max(left2[i] + right1[d - i - 1], right2[i] + left1[d - i - 1]));
    return ans;
}

Compilation message

grader.cpp: In function 'int main()':
grader.cpp:7:12: warning: variable 'n_s' set but not used [-Wunused-but-set-variable]
     int i, n_s;
            ^~~

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1131 ms 13552 KB Output is correct
2 Correct 894 ms 13372 KB Output is correct
3 Correct 1189 ms 13424 KB Output is correct
4 Correct 959 ms 13444 KB Output is correct
5 Correct 1430 ms 11168 KB Output is correct
6 Correct 424 ms 11136 KB Output is correct
7 Correct 724 ms 8764 KB Output is correct
8 Correct 936 ms 8828 KB Output is correct
9 Correct 294 ms 12544 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 4748 KB Output is correct
2 Correct 29 ms 4836 KB Output is correct
3 Correct 22 ms 4864 KB Output is correct
4 Correct 27 ms 4680 KB Output is correct
5 Correct 27 ms 4608 KB Output is correct
6 Correct 13 ms 4480 KB Output is correct
7 Correct 11 ms 4480 KB Output is correct
8 Correct 11 ms 4452 KB Output is correct
9 Correct 14 ms 4480 KB Output is correct

Subtask #4
53.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1198 ms 15732 KB Output is correct
2 Correct 1295 ms 15708 KB Output is correct
3 Correct 529 ms 6264 KB Output is correct
4 Correct 30 ms 4608 KB Output is correct
5 Correct 12 ms 4480 KB Output is correct
6 Correct 13 ms 4480 KB Output is correct
7 Correct 13 ms 4480 KB Output is correct
8 Correct 1537 ms 8812 KB Output is correct
9 Correct 1609 ms 8852 KB Output is correct