제출 #943516

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
943516		andrei_boaca	Sightseeing in Kyoto (JOI22_kyoto)	C++17	0 / 100	1 ms	604 KiB

kyoto

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
ll n,m;
ll A[100005],B[100005];
set<ll> lines,cols;
set<pair<ld,pii>> setik; /// 0 -> linie, 1 -> coloana
void elimlin(ll poz)
{
    auto it=lines.find(poz);
    ll st=0,dr=0;
    if(it!=lines.begin())
        st=*prev(it);
    it++;
    if(it!=lines.end())
        dr=(*it);
    lines.erase(poz);
    if(st!=0)
    {
        ld val=ld(A[poz]-A[st])/ld(poz-st);
        setik.erase({val,{poz,0}});
    }
    if(dr!=0)
    {
        ld val=ld(A[dr]-A[poz])/ld(dr-poz);
        setik.erase({val,{dr,0}});
    }
    if(st!=0&&dr!=0)
    {
        ld val=ld(A[dr]-A[st])/ld(dr-st);
        setik.insert({val,{dr,0}});
    }
}
void elimcol(ll poz)
{
    auto it=cols.find(poz);
    ll st=0,dr=0;
    if(it!=cols.begin())
        st=*prev(it);
    it++;
    if(it!=cols.end())
        dr=(*it);
    cols.erase(poz);
    if(st!=0)
    {
        ld val=ld(B[poz]-B[st])/ld(poz-st);
        setik.erase({val,{poz,1}});
    }
    if(dr!=0)
    {
        ld val=ld(B[dr]-B[poz])/ld(dr-poz);
        setik.erase({val,{dr,1}});
    }
    if(st!=0&&dr!=0)
    {
        ld val=ld(B[dr]-B[st])/ld(dr-st);
        setik.insert({val,{dr,1}});
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>A[i];
        lines.insert(i);
    }
    for(int i=1;i<=m;i++)
    {
        cin>>B[i];
        cols.insert(i);
    }
    ll cnt=2;
    ll x=n;
    ll y=m;
    for(int i=2;i<=n;i++)
        setik.insert({A[i]-A[i-1],{i,0}});
    for(int i=2;i<=m;i++)
        setik.insert({B[i]-B[i-1],{i,1}});
    ll ans=0;
    while(lines.size()>=2&&cols.size()>=2)
    {
        auto it=prev(setik.end());
        if((*it).second.second==0) /// linie
        {
            ll poz=(*it).second.first;
            if(poz==x)
                cnt--;
            if(cnt==0)
            {
                ll aux=*prev(cols.end());
                ans+=(y-aux)*A[poz];
                y=aux;
                cnt=1;
            }
            elimlin(poz);
        }
        else /// coloana
        {
            ll poz=(*it).second.first;
            if(poz==y)
                cnt--;
            if(cnt==0)
            {
                ll aux=*prev(lines.end());
                ans+=(x-aux)*B[poz];
                x=aux;
                cnt=1;
            }
            elimcol(poz);
        }
    }
    if(lines.size()==2)
        ans+=(x-1)*B[1]+(y-1)*A[*prev(lines.end())];
    else
        ans+=(x-1)*B[*prev(cols.end())]+(y-1)*A[1];
    cout<<ans;
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 30
• Subtask 3: 0 / 60