Submission #147810

#	Time	Username	Problem	Language	Result	Execution time	Memory
147810		willi19	Holiday (IOI14_holiday)	C++14	0 / 100	2574 ms	17180 KiB

holiday

#include<cstdio>
#include <bits/stdc++.h>
#include <holiday.h>
using namespace std;
long long dp_right[260000],dp_left[260000],sum;
int pointer;
multiset<long long,greater<long long> > trash;
multiset<long long> sel;
void dpopt_right(int tl,int tr,int left,int right,int start,int attraction[])
{
    printf("%d %d\n",tl,tr);
    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;
    pointer=left+1;//need this?
    for(;pointer<=right&&mid-pointer+start>0;pointer++)
    {
        sel.insert(attraction[pointer]);
        sum+=attraction[pointer];
        while(sel.size()>mid-pointer+start)
        {
            sum-=*sel.begin();
            trash.insert(*sel.begin());
            sel.erase(sel.begin());
        }
        if(dp_right[mid]<sum)
        {
            max_ind=pointer;
            dp_right[mid]=sum;
        }
    }
    pointer-=1;
    for(;pointer>max_ind;pointer--)
    {
        if(sel.find(attraction[pointer])==sel.end())
            trash.erase(trash.find(attraction[pointer]));
        else
        {
            sum-=attraction[pointer];
            sel.erase(sel.find(attraction[pointer]));
        }
    }
    if(tl==tr)
        return;
    dpopt_right(mid+1,tr,max_ind,right,start,attraction);
    for(;pointer>left;pointer--)
    {
        if(sel.find(attraction[pointer])==sel.end())
            trash.erase(trash.find(attraction[pointer]));
        else
        {
            sum-=attraction[pointer];
            sel.erase(sel.find(attraction[pointer]));
        }
    }
    dpopt_right(tl,mid-1,left,max_ind,start,attraction);
}
void dpopt_left(int tl,int tr,int left,int right,int start,int attraction[])
{
    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;
    pointer=right-1;
    for(;pointer>=left&&mid-(start-pointer)*2>0;pointer--)
    {
        sel.insert(attraction[pointer]);
        sum+=attraction[pointer];
        while(sel.size()>mid-(start-pointer)*2)
        {
            sum-=*sel.begin();
            trash.insert(*sel.begin());
            sel.erase(sel.begin());
        }
        if(dp_left[mid+2]<sum)
        {
            max_ind=pointer;
            dp_left[mid+2]=sum;
        }
    }
    pointer++;
    if(tl==tr)
        return;
    for(;pointer<max_ind;pointer++)
    {
        if(sel.find(attraction[pointer])==sel.end())
            trash.erase(trash.find(attraction[pointer]));
        else
        {
            sum-=attraction[pointer];
            sel.erase(sel.find(attraction[pointer]));
        }
    }
    dpopt_left(mid+1,tr,left,max_ind,start,attraction);
    for(;pointer<right;pointer++)
    {
        if(sel.find(attraction[pointer])==sel.end())
            trash.erase(trash.find(attraction[pointer]));
        else
        {
            sum-=attraction[pointer];
            sel.erase(sel.find(attraction[pointer]));
        }
    }
    dpopt_left(tl,mid-1,max_ind,right,start,attraction);
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
    long long ret=1;
    sel.insert(attraction[start]);
    pointer=start;
    sum=attraction[start];
    dpopt_right(1,d,start,n-1,start,attraction);
    if(start!=0)
    {
        sel.clear();
        trash.clear();
        sel.insert(attraction[start-1]);
        sum=attraction[start-1];
        pointer=start-1;
        dpopt_left(1,d-2,0,start-1,start-1,attraction);
    }
    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]);
    pointer=start;
    sum=attraction[start];
    dpopt_right(1,d,start,n-1,start,attraction);
    if(start!=0)
    {
        sel.clear();
        trash.clear();
        sel.insert(attraction[start-1]);
        sum=attraction[start-1];
        pointer=start-1;
        dpopt_left(1,d-2,0,start-1,start-1,attraction);
    }
    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*)':
holiday.cpp:15:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(sel.size()<mid-left+start)
        ~~~~~~~~~~^~~~~~~~~~~~~~~
holiday.cpp:17:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(sel.size()<mid-left+start&&!trash.empty())
               ~~~~~~~~~~^~~~~~~~~~~~~~~
holiday.cpp:24:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(sel.size()>mid-left+start)
        ~~~~~~~~~~^~~~~~~~~~~~~~~
holiday.cpp:26:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(sel.size()>mid-left+start)
               ~~~~~~~~~~^~~~~~~~~~~~~~~
holiday.cpp:40:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(sel.size()>mid-pointer+start)
               ~~~~~~~~~~^~~~~~~~~~~~~~~~~~
holiday.cpp: In function 'void dpopt_left(int, int, int, int, int, int*)':
holiday.cpp:83:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(sel.size()<mid-(start-right)*2)
        ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
holiday.cpp:85:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(sel.size()<mid-(start-right)*2&&!trash.empty())
               ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
holiday.cpp:92:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(sel.size()>mid-(start-right)*2)
        ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
holiday.cpp:94:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(sel.size()>mid-(start-right)*2)
               ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
holiday.cpp:108:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(sel.size()>mid-(start-pointer)*2)
               ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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