제출 #201882

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
201882		MKopchev	Cake 3 (JOI19_cake3)	C++14	24 / 100	4069 ms	13560 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++;
        }
    }
}
void to_remove(int positon)
{
    pair<int/*value*/,int/*position*/> current={inp[positon].first,positon};

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


    in--;
    sum_in-=current.first;
    if(in<m)sum_greatest=-1e18;
}
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;
        }

        for(int j=i+1;j<=n;j++)
            to_remove(j);
    }

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

컴파일 시 표준 에러 (stderr) 메시지

cake3.cpp: In function 'int main()':
cake3.cpp:71: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:74: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