Submission #547983

#	Time	Username	Problem	Language	Result	Execution time	Memory
547983		fcmalkcin	Sightseeing in Kyoto (JOI22_kyoto)	C++17	100 / 100	738 ms	29028 KiB

kyoto

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

#define ll long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define endl "\n"
#define pb push_back
#define F(i,a,b) for(ll i=a;i<=b;i++)

const ll maxn=5e5+100;
const ll base=300;
const ll mod= 1e9+7 ;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());




struct comp
{
    bool operator() (const pair<pll,pll> &a,const pair<pll,pll> &b) const
    {
        auto p=a.ff;
        auto p1=b.ff;
        if (p.ff*p1.ss>p1.ff*p.ss)
            return true;
        if (p.ff*p1.ss<p1.ff*p.ss)
            return false;
        return (a.ss>b.ss);
    }
};
set<ll> st[2];
ll a[maxn][2];
set<pair<pll,pll>,comp> stp;
ll pos[maxn];
ll val[maxn][2];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen("t.inp","r"))
    {
        freopen("test.inp","r",stdin);
        freopen("test.out","w",stdout);
    }
    ll n, m;
    cin>> n>> m;
    ll cnt=0;
    for (int i=1; i<=n; i++)
    {
        cin>> a[i][0];
        st[0].insert(i);
        if (i>=2)
            stp.insert(make_pair(make_pair(a[i][0]-a[i-1][0],1),make_pair(i,0)));
    }
    for (int i=1; i<=m; i++)
    {
        cin>> a[i][1];
        st[1].insert(i);
        if (i>=2)
            stp.insert(make_pair(make_pair(a[i][1]-a[i-1][1],1),make_pair(i,1)));
    }
    while (stp.size())
    {
        auto it=stp.begin();
        stp.erase(it);
        auto p=((*it).ss);
        ll t=p.ss;
        cnt++;
        val[p.ff][t]=cnt;
        st[t].erase(p.ff);
        auto it1=st[t].lower_bound(p.ff);

        if (it1!=st[t].end())
        {
            ll posnxt=(*it1);
            ll posnw=p.ff;
            it1--;
            ll pospre=(*it1);
            stp.erase(make_pair(make_pair(a[posnxt][t]-a[posnw][t],posnxt-posnw),make_pair(posnxt,t)));
            stp.insert(make_pair(make_pair(a[posnxt][t]-a[pospre][t],posnxt-pospre),make_pair(posnxt,t)));
        }
    }
    ll x=n;
    ll y=m;
    ll ans=0;
    while (max(x,y)!=1)
    {
        if (x==1)
        {
            ans+=a[x][0];
            y--;
        }
        else if (y==1)
        {
            ans+=a[y][1];
            x--;
        }
        else
        {
            if (val[x][0]>val[y][1])
            {
                ans+=a[x][0];
                y--;
            }
            else
            {
                ans+=a[y][1];
                x--;
            }
        }
    }
    cout <<ans<<endl;
}

Compilation message (stderr)

kyoto.cpp: In function 'int main()':
kyoto.cpp:47:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |         freopen("test.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
kyoto.cpp:48:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |         freopen("test.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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