oj.uz

Submission #857546

# Submission time Handle Problem Language Result Execution time Memory
857546 2023-10-06T11:36:44 Z abcvuitunggio Holiday (IOI14_holiday) C++17
100 / 100
 1329 ms 12116 KB 
#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
int n,s,d,a[100001],idx[100001],pos[100001];
long long p[250001][2];
pair <long long, int> st[400001];
void update(int node, int l, int r, int i){
    if (l>i||r<i||l>r)
        return;
    if (l==r){
        st[node].second^=1;
        st[node].first=st[node].second*a[i];
        return;
    }
    int mid=(l+r)>>1;
    update(node<<1,l,mid,i);
    update(node<<1|1,mid+1,r,i);
    st[node]={st[node<<1].first+st[node<<1|1].first,st[node<<1].second+st[node<<1|1].second};
}
long long get(int node, int l, int r, int x){
    if (st[node].second<=x)
        return st[node].first;
    int mid=(l+r)>>1;
    return (st[node<<1|1].second<x?get(node<<1,l,mid,x-st[node<<1|1].second)+st[node<<1|1].first:get(node<<1|1,mid+1,r,x));
}
void dnc(int l, int r, int optl, int optr, int idx){
    if (l>r||optl>optr)
        return;
    int mid=(l+r)>>1;
    pair <long long, int> tmp={0,-1e9};
    for (int i=optl;i<=min(s+mid/(idx+1),optr);i++){
        update(1,0,n-1,pos[i]);
        tmp=max(tmp,make_pair(get(1,0,n-1,mid-(i-s)*(idx+1)),-i));
    }
    p[mid][idx]=tmp.first;
    int opt=-tmp.second;
    for (int i=opt;i<=min(s+mid/(idx+1),optr);i++)
        update(1,0,n-1,pos[i]);
    dnc(mid+1,r,opt,optr,idx);
    for (int i=optl;i<opt;i++)
        update(1,0,n-1,pos[i]);
    dnc(l,mid-1,optl,opt,idx);
}
long long solve(){
    for (int i=0;i<n;i++)
        idx[i]=i;
    for (int i=0;i<=d;i++)
        p[i][0]=p[i][1]=0;
    sort(idx,idx+n,[](int i, int j){return make_pair(a[i],i)<make_pair(a[j],j);});
    sort(a,a+n);
    for (int i=0;i<n;i++)
        pos[idx[i]]=i;
    if (s<n-1){
        s++;
        dnc(0,d,s,n-1,0);
        s--;
    }
    reverse(pos,pos+n);
    s=n-1-s;
    dnc(0,d,s,n-1,1);
    long long res=0;
    for (int i=0;i<d;i++)
        res=max(res,p[i][0]+p[d-i-1][1]);
    return res;
}
long long findMaxAttraction(int N, int start, int D, int attraction[]){
    n=N;
    s=start;
    d=D;
    for (int i=0;i<n;i++)
        a[i]=attraction[i];
    long long res=solve();
    for (int i=0;i<n;i++)
        a[i]=attraction[n-i-1];
    s=n-start-1;
    return max(res,solve());
}

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1205 ms 11976 KB Output is correct
2 Correct 1169 ms 11864 KB Output is correct
3 Correct 1211 ms 11980 KB Output is correct
4 Correct 1158 ms 11976 KB Output is correct
5 Correct 1113 ms 12116 KB Output is correct
6 Correct 457 ms 8212 KB Output is correct
7 Correct 646 ms 9416 KB Output is correct
8 Correct 685 ms 9504 KB Output is correct
9 Correct 390 ms 8024 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 7200 KB Output is correct
2 Correct 22 ms 7004 KB Output is correct
3 Correct 22 ms 7144 KB Output is correct
4 Correct 21 ms 4956 KB Output is correct
5 Correct 19 ms 5092 KB Output is correct
6 Correct 5 ms 4956 KB Output is correct
7 Correct 4 ms 4956 KB Output is correct
8 Correct 4 ms 4984 KB Output is correct
9 Correct 4 ms 4956 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1243 ms 11976 KB Output is correct
2 Correct 1329 ms 12072 KB Output is correct
3 Correct 167 ms 9308 KB Output is correct
4 Correct 12 ms 4956 KB Output is correct
5 Correct 4 ms 4952 KB Output is correct
6 Correct 4 ms 4952 KB Output is correct
7 Correct 4 ms 4956 KB Output is correct
8 Correct 930 ms 11992 KB Output is correct
9 Correct 941 ms 12092 KB Output is correct