Submission #147787

#	Time	Username	Problem	Language	Result	Execution time	Memory
147787		willi19	Holiday (IOI14_holiday)	C++14	0 / 100	1679 ms	65540 KiB

holiday

#include<cstdio>
#include <bits/stdc++.h>
#include <holiday.h>
using namespace std;
long long dp_right[260000],dp_left[260000];
void dpopt_right(int tl,int tr,int left,int right,int start,int attraction[],multiset<long long> sel,multiset<long long,greater<long long> > trash,long long sum)
{
    int mid=(tl+tr)/2;
    if(tl>tr)
        return;
    if(sel.size()<mid-left+start)
    {
        while(sel.size()<mid-left+start&&!trash.empty())
        {
            sum+=*trash.begin();
            sel.insert(*trash.begin());
            trash.erase(trash.begin());
        }
    }
    if(sel.size()>mid-left+start)
    {
        while(sel.size()>mid-left+start)
        {
            sum-=*sel.begin();
            trash.insert(*sel.begin());
            sel.erase(sel.begin());
        }
    }
    dp_right[mid]=sum;
    int max_ind=left;
    int i=left+1;
    for(;i<=right&&mid-i+start>0;i++)
    {
        sel.insert(attraction[i]);
        sum+=attraction[i];
        while(sel.size()>mid-i+start)
        {
            sum-=*sel.begin();
            trash.insert(*sel.begin());
            sel.erase(sel.begin());
        }
        if(dp_right[mid]<sum)
        {
            max_ind=i;
            dp_right[mid]=sum;
        }
    }
    for(i--;i>max_ind;i--)
    {
        if(sel.find(attraction[i])==sel.end())
            trash.erase(trash.find(attraction[i]));
        else
        {
            sum-=attraction[i];
            sel.erase(sel.find(attraction[i]));
        }
    }
    if(tl==tr)
        return;
    dpopt_right(mid+1,tr,max_ind,right,start,attraction,sel,trash,sum);
    for(int i=max_ind;i>left;i--)
    {
        if(sel.find(attraction[i])==sel.end())
            trash.erase(trash.find(attraction[i]));
        else
        {
            sum-=attraction[i];
            sel.erase(sel.find(attraction[i]));
        }
    }
    dpopt_right(tl,mid-1,left,max_ind,start,attraction,sel,trash,sum);
}
void dpopt_left(int tl,int tr,int left,int right,int start,int attraction[],multiset<long long> sel,multiset<long long,greater<long long> > trash,long long sum)
{
    if(start==-1||tl>tr)
        return;
    int mid=(tl+tr)/2;
    if(sel.size()<mid-(start-right)*2)
    {
        while(sel.size()<mid-(start-right)*2&&!trash.empty())
        {
            sum+=*trash.begin();
            sel.insert(*trash.begin());
            trash.erase(trash.begin());
        }
    }
    if(sel.size()>mid-(start-right)*2)
    {
        while(sel.size()>mid-(start-right)*2)
        {
            sum-=*sel.begin();
            trash.insert(*sel.begin());
            sel.erase(sel.begin());
        }
    }
    dp_left[mid+2]=sum;
    int max_ind=right;
    int i=right-1;
    for(;i>=left&&mid-(start-i)*2>0;i--)
    {
        sel.insert(attraction[i]);
        sum+=attraction[i];
        while(sel.size()>mid-(start-i)*2)
        {
            sum-=*sel.begin();
            trash.insert(*sel.begin());
            sel.erase(sel.begin());
        }
        if(dp_left[mid+2]<sum)
        {
            max_ind=i;
            dp_left[mid+2]=sum;
        }
    }
    if(tl==tr)
        return;
    for(i++;i<max_ind;i++)
    {
        if(sel.find(attraction[i])==sel.end())
            trash.erase(trash.find(attraction[i]));
        else
        {
            sum-=attraction[i];
            sel.erase(sel.find(attraction[i]));
        }
    }
    dpopt_left(mid+1,tr,left,max_ind,start,attraction,sel,trash,sum);
    for(int i=max_ind;i<right;i++)
    {
        if(sel.find(attraction[i])==sel.end())
            trash.erase(trash.find(attraction[i]));
        else
        {
            sum-=attraction[i];
            sel.erase(sel.find(attraction[i]));
        }
    }
    dpopt_left(tl,mid-1,max_ind,right,start,attraction,sel,trash,sum);
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
    long long ret=1;
    multiset<long long>sel;
    sel.insert(attraction[start]);
    multiset<long long,greater<long long> > trash;
    dpopt_right(1,d,start,n-1,start,attraction,sel,trash,attraction[start]);
    if(start!=0)
    {
        sel.clear();
        trash.clear();
        sel.insert(attraction[start-1]);
        dpopt_left(1,d-2,0,start-1,start-1,attraction,sel,trash,attraction[start-1]);
    }
    for(int i=0;i<=d;i++)
        ret=max(ret,dp_right[i]+dp_left[d-i]);
    for(int i=0;i<n-i-1;i++)
        swap(attraction[i],attraction[n-i-1]);
    start=n-1-start;
    sel.clear();
    trash.clear();
    sel.insert(attraction[start]);
    dpopt_right(1,d,start,n-1,start,attraction,sel,trash,attraction[start]);
    if(start!=0)
    {
        sel.clear();
        trash.clear();
        sel.insert(attraction[start-1]);
        dpopt_left(1,d-2,0,start-1,start-1,attraction,sel,trash,attraction[start-1]);
    }
    for(int i=0;i<=d;i++)
        ret=max(ret,dp_right[i]+dp_left[d-i]);
    return ret;
}

Compilation message (stderr)

holiday.cpp: In function 'void dpopt_right(int, int, int, int, int, int*, std::multiset<long long int>, std::multiset<long long int, std::greater<long long int> >, long long int)':
holiday.cpp:11:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(sel.size()<mid-left+start)
        ~~~~~~~~~~^~~~~~~~~~~~~~~
holiday.cpp:13:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(sel.size()<mid-left+start&&!trash.empty())
               ~~~~~~~~~~^~~~~~~~~~~~~~~
holiday.cpp:20:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(sel.size()>mid-left+start)
        ~~~~~~~~~~^~~~~~~~~~~~~~~
holiday.cpp:22:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(sel.size()>mid-left+start)
               ~~~~~~~~~~^~~~~~~~~~~~~~~
holiday.cpp:36:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(sel.size()>mid-i+start)
               ~~~~~~~~~~^~~~~~~~~~~~
holiday.cpp: In function 'void dpopt_left(int, int, int, int, int, int*, std::multiset<long long int>, std::multiset<long long int, std::greater<long long int> >, long long int)':
holiday.cpp:78:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(sel.size()<mid-(start-right)*2)
        ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
holiday.cpp:80:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(sel.size()<mid-(start-right)*2&&!trash.empty())
               ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
holiday.cpp:87:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(sel.size()>mid-(start-right)*2)
        ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
holiday.cpp:89:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(sel.size()>mid-(start-right)*2)
               ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
holiday.cpp:103:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(sel.size()>mid-(start-i)*2)
               ~~~~~~~~~~^~~~~~~~~~~~~~~~

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