oj.uz

Submission #294128

# Submission time Handle Problem Language Result Execution time Memory
294128 2020-09-08T15:45:14 Z alexandra_udristoiu Holiday (IOI14_holiday) C++14
100 / 100
 1980 ms 19064 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 376 KB Output is correct
7 Correct 0 ms 384 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1669 ms 16120 KB Output is correct
2 Correct 1227 ms 16248 KB Output is correct
3 Correct 1681 ms 16120 KB Output is correct
4 Correct 1240 ms 16216 KB Output is correct
5 Correct 1980 ms 13052 KB Output is correct
6 Correct 691 ms 9848 KB Output is correct
7 Correct 1076 ms 8024 KB Output is correct
8 Correct 1280 ms 8632 KB Output is correct
9 Correct 556 ms 11308 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 888 KB Output is correct
2 Correct 31 ms 888 KB Output is correct
3 Correct 28 ms 924 KB Output is correct
4 Correct 27 ms 640 KB Output is correct
5 Correct 26 ms 640 KB Output is correct
6 Correct 6 ms 512 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1798 ms 18744 KB Output is correct
2 Correct 1937 ms 19064 KB Output is correct
3 Correct 546 ms 3704 KB Output is correct
4 Correct 19 ms 512 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 1892 ms 7456 KB Output is correct
9 Correct 1921 ms 7672 KB Output is correct