oj.uz

답안 #875421

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
875421 2023-11-19T16:17:11 Z Denkata Cake 3 (JOI19_cake3) C++14
0 / 100
 1 ms 2652 KB 
#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 <ll> vals;
set <ll> :: iterator it;
ll sum = 0;
bool fl = false;
int l,r;
void add(ll val)
{
    if(vals.size()<m-2)
    {
        vals.insert(val);
        sum+=val;
        if(vals.size()==m-2)
            fl = true,it = vals.begin();
        return ;
    }
    vals.insert(val);//dano ne pravi problemi s it
    if(*it<val)
    {
        sum -= *it;
        sum += val;
        it++;
    }
}
void rem(ll val)
{
    if(vals.size()<=m-2)
    {
        vals.erase(val);
        sum-=val;
        fl = false;
        return ;
    }
    //dano ne pravi problemi s it
    if(*it>val)
    {
        vals.erase(val);
    }
    if(*it<=val)
    {
        sum -= val;
        it--;
        sum+=*it;
        vals.erase(val);
    }

}
void activate(int ll,int rr)
{
    while(r<rr)
    {
        r++;
        add(v[r]);
    }
    //cout<<l<<" "<<r<<" "<<sum<<endl;
    while(ll<l)
    {
        l--;
        add(v[l]);
    }
    //cout<<l<<" "<<r<<" "<<sum<<endl;
    while(ll>l)
    {
        rem(v[l]);
        l++;
    }
    //cout<<l<<" "<<r<<" "<<sum<<endl;
    while(rr<r)
    {
        rem(v[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 = 0;
    int pos = optl;
    for(int i=optl;i<=min(mid,optr);i++)
    {
       // cout<<i+1<<" "<<mid-1<<" managed :"<<endl;
        if(i+1<=mid-1)activate(i+1,mid-1);
        if(fl && i+1<=mid-1)
        {
            ll tek = v[i]+v[mid]+sum - 2*(c[mid] - c[i]);
         //   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]);
    it = vals.begin();
    solve(1,n,1,n);
    cout<<overall<<endl;
    return 0;
}

Compilation message

cake3.cpp: In function 'void add(ll)':
cake3.cpp:14:19: warning: comparison of integer expressions of different signedness: 'std::set<long long 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<long long 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)':
cake3.cpp:32:19: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   32 |     if(vals.size()<=m-2)
      |        ~~~~~~~~~~~^~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2648 KB Output is correct
12 Correct 1 ms 2392 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Incorrect 1 ms 2520 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2648 KB Output is correct
12 Correct 1 ms 2392 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Incorrect 1 ms 2520 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #3
0 / 76.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2648 KB Output is correct
12 Correct 1 ms 2392 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Incorrect 1 ms 2520 KB Output isn't correct
18 Halted 0 ms 0 KB -