Submission #294128

#	Time	Username	Problem	Language	Result	Execution time	Memory
294128		alexandra_udristoiu	Holiday (IOI14_holiday)	C++14	100 / 100	1980 ms	19064 KiB

holiday

#include"holiday.h"
#include<algorithm>
#define DIM 100005
#define DIM2 250005
#define f first
#define s second
using namespace std;
int v[DIM], nr;
long long dp[DIM2], e[2][DIM2], e2[2][DIM2];
pair<int, int> w[DIM];
pair<long long, int> aint[4 * DIM];
void copiere(long long a[], long long b[], int d){
    for(int i = 1; i <= d; i++){
        a[i] = b[i];
    }
}
void build(int n){
    for(int i = 1; i <= 4 * n; i++){
        aint[i] = make_pair(0, 0);
    }
}
void update(int nod, int st, int dr, int p, int val){
    if(st == dr){
        aint[nod].s = val;
        aint[nod].f = val * w[st].f;
    }
    else{
        int mid = (st + dr) / 2;
        if(p <= mid){
            update(2 * nod, st, mid, p, val);
        }
        else{
            update(2 * nod + 1, mid + 1, dr, p, val);
        }
        aint[nod].f = aint[2 * nod].f + aint[2 * nod + 1].f;
        aint[nod].s = aint[2 * nod].s + aint[2 * nod + 1].s;
    }
}
long long query(int nod, int st, int dr, int nr){
    if(aint[nod].s <= nr){
        return aint[nod].f;
    }
    else{
        int mid = (st + dr) / 2;
        if(aint[2 * nod + 1].s >= nr){
            return query(2 * nod + 1, mid + 1, dr, nr);
        }
        else{
            return aint[2 * nod + 1].f + query(2 * nod, st, mid, nr - aint[2 * nod + 1].s);
        }
    }
}
void solve(int p, int u, int st, int dr, int ad){
    if(p > u){
        return;
    }
    int i, mid, x = 0;
    long long sol = 0, val;
    mid = (p + u) / 2;
    for(i = st; i <= dr; i++){
        update(1, 1, nr, v[i], 1);
        if(i * ad <= mid){
            val = query(1, 1, nr, mid - i * ad);
            if(val > sol){
                sol = val;
                x = i;
            }
        }
    }
    dp[mid] = sol;
    for(i = st; i <= dr; i++){
        update(1, 1, nr, v[i], 0);
    }
    solve(p, mid - 1, st, x, ad);
    for(i = st; i < x; i++){
        update(1, 1, nr, v[i], 1);
    }
    solve(mid + 1, u, x, dr, ad);
    for(i = st; i < x; i++){
        update(1, 1, nr, v[i], 0);
    }
}

long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
    int i, j;
    long long sol = 0;

    if(start != n - 1){
        nr = 0;
        for(i = start + 1; i < n; i++){
            w[++nr] = make_pair(attraction[i], i - start);
        }
        sort(w + 1, w + nr + 1);
        build(nr);
        for(i = 1; i <= nr; i++){
            v[ w[i].s ] = i;
        }
        solve(1, d, 1, nr, 1);
        copiere(e[0], dp, d);
        solve(1, d, 1, nr, 2);
        copiere(e[1], dp, d);
    }

    if(start != 0){
        nr = 0;
        for(i = start - 1; i >= 0; i--){
            w[++nr] = make_pair(attraction[i], start - i);
        }
        sort(w + 1, w + nr + 1);
        build(nr);
         for(i = 1; i <= nr; i++){
            v[ w[i].s ] = i;
        }
        solve(1, d, 1, nr, 1);
        copiere(e2[0], dp, d);
        solve(1, d, 1, nr, 2);
        copiere(e2[1], dp, d);
    }

    for(i = 1; i <= d; i++){
        e[0][i] = max(e[0][i], e[0][i - 1]);
        e[1][i] = max(e[1][i], e[1][i - 1]);
        e2[0][i] = max(e2[0][i], e2[0][i - 1]);
        e2[1][i] = max(e2[1][i], e2[1][i - 1]);
    }
    for(i = d; i >= 1; i--){
        e[0][i] = max(e[0][i], e[0][i - 1] + attraction[start]);
        e[1][i] = max(e[1][i], e[1][i - 1] + attraction[start]);
    }
    for(i = 0; i <= d; i++){
        sol = max(sol, e[0][i] + e2[1][d - i]);
        sol = max(sol, e[1][i] + e2[0][d - i]);
    }
    return sol;
}

Compilation message (stderr)

holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:85:12: warning: unused variable 'j' [-Wunused-variable]
   85 |     int i, j;
      |            ^

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 17 / 17
• Subtask 4: 53 / 53