Submission #93808

#	Time	Username	Problem	Language	Result	Execution time	Memory
93808		Bodo171	Holiday (IOI14_holiday)	C++14	47 / 100	5084 ms	4728 KiB

holiday

#include"holiday.h"
#include <iostream>
#include <algorithm>
using namespace std;
const int nmax=100005;
pair<long long,long long> aib[nmax];
long long ans;
pair<int,int> norm[nmax];
int wh[nmax],v[nmax];
int n,D;
inline int lbit(int x)
{
    return ((x^(x-1))&x);
}
void update(int poz,long long v1,long long v2)
{
    for(int idx=poz;idx<=n;idx+=lbit(idx))
            aib[idx].first+=v1,aib[idx].second+=v2;
}
long long find_kth(int k)
{
    int cat=0,poz=0;
    long long ret=0;
    for(int p=17;p>=0;p--)
    {
        if(poz+(1<<p)<=n&&cat+aib[poz+(1<<p)].first<=k)
        {
            poz+=(1<<p);
            cat+=aib[poz].first;
            ret+=aib[poz].second;
        }
    }
    return ret;
}
void add(int poz)
{
    update(wh[poz],1,v[poz]);
}
void rem(int poz)
{
    update(wh[poz],-1,-v[poz]);
}
void qr(int st,int dr,int m)
{
    ans=max(ans,find_kth(D-2*(dr-m)-(m-st)));
}
void solve(int s)
{
    for(int i=s;i<=n;i++)
    {
        add(i);
        qr(s,i,s);
        for(int j=s-1;j>=1;j--)
        {
            add(j);
            qr(j,i,s);
        }
        for(int j=s-1;j>=1;j--)
            rem(j);
    }
    for(int i=s;i<=n;i++)
        rem(i);
}
long long int findMaxAttraction(int N, int start, int d, int attraction[]) {
    n=N;
    for(int i=1;i<=n;i++)
        v[i]=attraction[i-1];
    for(int i=1;i<=n;i++)
        norm[i].first=v[i],norm[i].second=i;
    sort(norm+1,norm+n+1);
    for(int i=1;i<=n;i++)
        wh[norm[i].second]=n-i+1;
    D=d;
    start++;
    solve(start);
    for(int i=1;i<=n/2;i++)
        swap(v[i],v[n-i+1]),swap(wh[i],wh[n-i+1]);
    solve(n-start+1);
    return ans;
}

Compilation message (stderr)

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 / 7
• Subtask 2: 23 / 23
• Subtask 3: 17 / 17
• Subtask 4: 0 / 53