Submission #201876

#	Time	Username	Problem	Language	Result	Execution time	Memory
201876		MKopchev	Cake 3 (JOI19_cake3)	C++14	24 / 100	4050 ms	17120 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);
        it++;
        if(in==m)sum_greatest=sum_in;
    }
    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++;
        }
    }
}

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);

    for(int i=1;i<=m;i++)active.insert({-1e9,i});
    it=active.begin();

    long long output=-1e18;
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            long long current=inp[j].first+inp[i].first-2*(inp[j].second-inp[i].second);
            if(in<m)current=-1e18;
            else current+=sum_greatest;
            output=max(output,current);
            to_add(j);
            //cout<<i<<" "<<j<<" -> "<<in<<" "<<sum_in<<" "<<sum_greatest<<" "<<current<<endl;
        }

        in=0;
        sum_in=0;
        sum_greatest=-1e18;
        for(int j=i;j<=n;j++)
        {
            active.erase({inp[j].first,j});
        }
        it=active.begin();
    }

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

Compilation message (stderr)

cake3.cpp: In function 'int main()':
cake3.cpp:49: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:52: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: 0 / 76