제출 #875426

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
875426		Denkata	Cake 3 (JOI19_cake3)	C++14	0 / 100	1 ms	2396 KiB

cake3

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5+3;
ll i,j,p,q,n,m,k,v[maxn],c[maxn];
pair <ll,ll> inp[maxn];
set < pair <ll,int> > vals;
set < pair<ll,int> > :: iterator it;
ll sum = 0;
bool fl = false;
int l,r;
void add(ll val,int ind)
{
    if(vals.size()<m-2)
    {
        vals.insert({val,ind});
        sum+=val;
        if(vals.size()==m-2)
            fl = true,it = vals.begin();
        return ;
    }
    if((*it).first>=val)
        vals.insert({val,ind});//dano ne pravi problemi s it
    if((*it).first<val)
    {
        sum -= (*it).first;
        sum += val;
        vals.insert({val,ind});
        it++;
    }
}
void rem(ll val,int ind)
{
    if(vals.size()<=m-2)
    {
        vals.erase({val,ind});
        sum-=val;
        fl = false;
        return ;
    }
    //dano ne pravi problemi s it
    if((*it).first>val)
    {
        vals.erase({val,ind});
    }
    if((*it).first<=val)
    {
        sum -= val;
        it--;
        sum+=(*it).first;
        vals.erase({val,ind});
    }

}
void activate(int ll,int rr)
{
    while(r<rr)
    {
        r++;
        add(v[r],r);
    }
    //cout<<l<<" "<<r<<" "<<sum<<endl;
    while(ll<l)
    {
        l--;
        add(v[l],l);
    }
    //cout<<l<<" "<<r<<" "<<sum<<endl;
    while(ll>l)
    {
        rem(v[l],l);
        l++;
    }
    //cout<<l<<" "<<r<<" "<<sum<<endl;
    while(rr<r)
    {
        rem(v[r],r);
        r--;
    }
    //cout<<l<<" "<<r<<" "<<sum<<endl;
    //cout<<fl<<" "<<sum<<endl;
}
ll overall;
void solve(int l,int r,int optl,int optr)
{
    if(r<l)return;
    int mid = (l+r)/2;
    ll ans = -1e18;
    int pos;
    for(int i=optl; i<=min(mid,optr); i++)
    {
        // cout<<i+1<<" "<<mid-1<<" managed :"<<endl;
        ll tek =v[i]+v[mid] - 2*(c[mid] - c[i]);
        if(i+1<=mid-1)activate(i+1,mid-1);
        if(fl)
            tek+=sum;
        else tek-=1e18;
        //   cout<<tek<<endl;
        if(tek>ans)
        {
            pos = i;
            ans = tek;
        }
    }
    overall = max(overall,ans);
    solve(l,mid-1,optl,pos);
    solve(mid+1,r,pos,optr);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>m;
    for(i=1; i<=n; i++)
    {
        cin>>inp[i].second>>inp[i].first;

    }
    //cout<<endl;
    sort(inp+1,inp+n+1);
    for(i=1; i<=n; i++)
    {
        v[i] = inp[i].second;
        c[i] = inp[i].first;
        //  cout<<v[i]<<" "<<c[i]<<endl;
    }
    sum = v[1];
    l=r=1;
    vals.insert({v[1],1});
    it = vals.begin();
    solve(1,n,1,n);
    cout<<overall<<endl;
    return 0;
}

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

cake3.cpp: In function 'void add(ll, int)':
cake3.cpp:14:19: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   14 |     if(vals.size()<m-2)
      |        ~~~~~~~~~~~^~~~
cake3.cpp:18:23: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   18 |         if(vals.size()==m-2)
      |            ~~~~~~~~~~~^~~~~
cake3.cpp: In function 'void rem(ll, int)':
cake3.cpp:34:19: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   34 |     if(vals.size()<=m-2)
      |        ~~~~~~~~~~~^~~~~
cake3.cpp: In function 'void solve(int, int, int, int)':
cake3.cpp:106:10: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
  106 |     solve(l,mid-1,optl,pos);
      |     ~~~~~^~~~~~~~~~~~~~~~~~

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