Submission #201896

#	Time	Username	Problem	Language	Result	Execution time	Memory
201896		MKopchev	Cake 3 (JOI19_cake3)	C++14	100 / 100	3400 ms	15352 KiB

cake3

#include<bits/stdc++.h>
using namespace std;
const int nmax=2e5+42;
int n,m;
pair<int/*v*/,int/*c*/> inp[nmax];
bool cmp(pair<int/*v*/,int/*c*/> a,pair<int/*v*/,int/*c*/> b)
{
    return a.second<b.second;
}

int in=0;
long long sum_in=0,sum_greatest=-1e18;

set< pair<int/*value*/,int/*position*/> > active;
set< pair<int/*value*/,int/*position*/> >::iterator it;

void to_add(int positon)
{
    pair<int/*value*/,int/*position*/> current={inp[positon].first,positon};
    in++;
    sum_in+=current.first;

    if(in<=m)
    {
        active.insert(current);
        if(in==m)
        {
            sum_greatest=sum_in;
            it=active.begin();
        }
    }
    else
    {
        if(current<(*it))//current is less than the greatest m values
        {
            active.insert(current);
        }
        else//current is greater than some of the greatest m values
        {
            sum_greatest-=(*it).first;

            active.insert(current);
            sum_greatest+=current.first;

            it++;
        }
    }
}
void to_remove(int positon)
{
    pair<int/*value*/,int/*position*/> current={inp[positon].first,positon};

    in--;
    sum_in-=current.first;
    if(in<m)sum_greatest=-1e18;

    if(in>=m)
    {
        if(current<(*it))//current is less than the greatest m values
        {
            active.erase(current);
        }
        else//current is greater than some of the greatest m values
        {
            sum_greatest-=(current).first;
            it--;

            active.erase(current);

            sum_greatest+=(*it).first;
        }
    }
    else
    {
        active.erase(current);
    }
}

long long output=-1e18;

int left_pointer=1,right_pointer=0;

void make_active(int l,int r)
{
    l++;
    r--;

    while(left_pointer>l)
    {
        left_pointer--;
        to_add(left_pointer);
    }

    while(right_pointer<r)
    {
        right_pointer++;
        to_add(right_pointer);
    }

    while(left_pointer<l)
    {
        to_remove(left_pointer);
        left_pointer++;
    }

    while(right_pointer>r)
    {
        to_remove(right_pointer);
        right_pointer--;
    }
}
void divide_and_conquer(int l,int r,int answer_left,int answer_right)
{
    if(l>r)return;

    int av=(l+r)/2;
    int best_position=answer_left;
    long long best_answer=-1e18;

    for(int j=answer_left;j<=answer_right&&j<av;j++)
    {
        make_active(j,av);

        long long current=inp[av].first+inp[j].first-2*(inp[av].second-inp[j].second);
        if(in<m)current=-1e18;
        else current+=sum_greatest;

        if(best_answer<current)
        {
            best_answer=current;
            best_position=j;
        }
        //cout<<j<<" "<<av<<" -> "<<in<<" "<<sum_in<<" "<<sum_greatest<<" "<<current<<endl;
        output=max(output,current);
    }

    divide_and_conquer(l,av-1,answer_left,best_position);
    divide_and_conquer(av+1,r,best_position,answer_right);
}
int main()
{
    scanf("%i%i",&n,&m);
    m=m-2;

    for(int i=1;i<=n;i++)scanf("%i%i",&inp[i].first,&inp[i].second);
    sort(inp+1,inp+n+1,cmp);

    it=active.begin();

    divide_and_conquer(1,n,1,n);

    printf("%lld\n",output);
    return 0;
}

Compilation message (stderr)

cake3.cpp: In function 'int main()':
cake3.cpp:142:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i%i",&n,&m);
     ~~~~~^~~~~~~~~~~~~~
cake3.cpp:145:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1;i<=n;i++)scanf("%i%i",&inp[i].first,&inp[i].second);
                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 19 / 19
• Subtask 3: 76 / 76