oj.uz

Submission #147857

# Submission time Handle Problem Language Result Execution time Memory
147857 2019-08-31T02:36:28 Z willi19 Holiday (IOI14_holiday) C++14
100 / 100
 2465 ms 10360 KB 
#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[])
{
    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--;
    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_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;
    if(start!=0)
    {
    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]);
        //printf("%lld %lld\n",dp_right[i],dp_left[d-i]);
    }
    for(int i=0;i<n-i-1;i++)
    {
        long long tmp=attraction[i];
        attraction[i]=attraction[n-i-1];
        attraction[n-i-1]=tmp;
    }
    start=n-1-start;
    sel.clear();
    trash.clear();
    sel.insert(attraction[start]);
    pointer=start;
    sum=attraction[start];
    for(int i=0;i<=d;i++)
        dp_left[i]=dp_right[i]=0;
    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<=d;i++)
    {
        ret=max(ret,dp_right[i]+dp_left[d-i]);
        //printf("%lld %lld\n",dp_right[i],dp_left[d-i]);
    }
    return ret;
    }
    else
    {
        multiset<long long> s;
    long long ret=0;
    for(int i=0;i<(d+1)/2&&start<n;i++,start++)
    {
        s.insert(attraction[start]);
        ret+=attraction[start];
    }
    long long state=ret;
    d=d/2;
    while(start<n&&d>0)
    {
        s.insert(attraction[start]);
        state+=attraction[start];
        while(s.size()>d)
        {
            state-=*(s.begin());
            s.erase(s.begin());
        }
        ret=max(ret,state);
        start++;
        d--;
    }
    return ret;
    }
}

Compilation message

holiday.cpp: In function 'void dpopt_right(int, int, int, int, int, int*)':
holiday.cpp:14:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(sel.size()<mid-left+start)
        ~~~~~~~~~~^~~~~~~~~~~~~~~
holiday.cpp:16:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(sel.size()<mid-left+start&&!trash.empty())
               ~~~~~~~~~~^~~~~~~~~~~~~~~
holiday.cpp:23:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(sel.size()>mid-left+start)
        ~~~~~~~~~~^~~~~~~~~~~~~~~
holiday.cpp:25:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(sel.size()>mid-left+start)
               ~~~~~~~~~~^~~~~~~~~~~~~~~
holiday.cpp:39: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:82:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(sel.size()<mid-(start-right)*2)
        ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
holiday.cpp:84:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(sel.size()<mid-(start-right)*2&&!trash.empty())
               ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
holiday.cpp:91:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(sel.size()>mid-(start-right)*2)
        ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
holiday.cpp:93:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(sel.size()>mid-(start-right)*2)
               ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
holiday.cpp:107:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(sel.size()>mid-(start-pointer)*2)
               ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:216:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(s.size()>d)
               ~~~~~~~~^~

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 5624 KB Output is correct
2 Correct 39 ms 5596 KB Output is correct
3 Correct 39 ms 5624 KB Output is correct
4 Correct 41 ms 5624 KB Output is correct
5 Correct 45 ms 3964 KB Output is correct
6 Correct 14 ms 1788 KB Output is correct
7 Correct 25 ms 2812 KB Output is correct
8 Correct 28 ms 2652 KB Output is correct
9 Correct 10 ms 1404 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 632 KB Output is correct
2 Correct 33 ms 632 KB Output is correct
3 Correct 28 ms 632 KB Output is correct
4 Correct 46 ms 504 KB Output is correct
5 Correct 41 ms 512 KB Output is correct
6 Correct 11 ms 376 KB Output is correct
7 Correct 8 ms 376 KB Output is correct
8 Correct 9 ms 376 KB Output is correct
9 Correct 10 ms 376 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2316 ms 10360 KB Output is correct
2 Correct 46 ms 6264 KB Output is correct
3 Correct 324 ms 1656 KB Output is correct
4 Correct 24 ms 380 KB Output is correct
5 Correct 9 ms 376 KB Output is correct
6 Correct 9 ms 376 KB Output is correct
7 Correct 10 ms 376 KB Output is correct
8 Correct 2465 ms 4768 KB Output is correct
9 Correct 2420 ms 4808 KB Output is correct