Submission #1095752

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095752		simona1230	Joker (BOI20_joker)	C++17	0 / 100	2 ms	6488 KiB

Joker

#include <bits/stdc++.h>
using namespace std;

struct human
{
    int a,b;
    human(){}
    human(int _a,int _b)
    {
        a=_a;
        b=_b;
    }
};

int n,maxx;
human h[200001];

bool cmp(human h1,human h2)
{
    return h1.a<h2.a;
}

void read()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>h[i].a>>h[i].b;
        maxx=max(maxx,h[i].b);
    }
    
    sort(h+1,h+n+1,cmp);
}

struct line
{
    int a,b;
    line(){}
    line(int _a,int _b)
    {
        a=_a;
        b=_b;
    }
    
    int value(int x)
    {
        return a*x+b;
    }
};

int sq;
vector<line> v[200001];

int query(int b,int x)
{
    if(v[b].size()==0)return 0;
    if(v[b].size()==1)return v[b][0].value(x);
    int ans=0;
    int l=0,r=v[b].size()-2;
    while(l<=r)
    {
        int m=(l+r)/2;
        if(v[b][m].value(x)>v[b][m+1].value(x))
        {
            ans=max(ans,v[b][m].value(x));
            r=m-1;
        }
        else
        {
            ans=max(ans,v[b][m+1].value(x));
            l=m+2;
        }
    }
    
    return ans;
}

double intersect(line l1,line l2)
{
    return (double)(l2.b-l1.b)/(double)(l1.a-l2.a);
}

void add_to(int b,line l)
{
    while(v[b].size()>=2&&intersect(v[b][v[b].size()-1],l)<intersect(v[b][v[b].size()-2],l))v[b].pop_back();
    v[b].push_back(l);
}

int add[200001];
int cnt[200001];

void solve()
{
    int ans=0;
    sq=sqrt(maxx);
    
    int k=maxx/sq;
    if(maxx%sq)k++;
    
    for(int i=1;i<=n;i++)
    {
        cnt[h[i].b]++;
        int b=h[i].b/sq;
        if(h[i].b%sq)b++;
        
        add[b]++;
        vector<line> in;
        int till=0;
        
        for(int j=min(maxx,b*sq);j>=(b-1)*sq+1;j--)
        {
            till+=cnt[j];
            in.push_back({j,till*j});
        }
        
        for(int j=in.size()-1;j>=0;j--)
            add_to(b,in[j]);
        
        till=0;
        int As=0;
        if(i!=n)As=(h[i+1].a*(n-i));
        for(int j=k;j>=1;j--)
        {
            ans=max(ans,query(j,till)+As);
            //cout<<(j-1)*sq<<" "<<j*sq<<" "<<query(j,till)<<endl;
            till+=add[j];
        }
        //cout<<i<<" ! "<<ans<<" "<<h[i].a<<" "<<h[i].b<<endl;
    }
    
    cout<<ans<<endl;
}

int main() 
{
    read();
    solve();
    return 0;
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 8
• Subtask 3: 0 / 25
• Subtask 4: 0 / 10
• Subtask 5: 0 / 22
• Subtask 6: 0 / 29