Submission #1182700

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182700		12345678	Sightseeing in Kyoto (JOI22_kyoto)	C++20	100 / 100	25 ms	5192 KiB

kyoto

#include <bits/stdc++.h>

using namespace std;

const int nx=1e5+5;

#define ll long long

ll h, w, a[nx], b[nx], ca, cb, res;

struct info
{
    ll x, y;
    info(ll x, ll y): x(x), y(y){}
    bool operator < (const info &o) const {return x*o.y<o.x*y;}
};
deque<info> A, B;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>h>>w;
    for (int i=1; i<=h; i++) cin>>a[i];
    for (int i=1; i<=w; i++) cin>>b[i];
    for (int i=2; i<=h; i++)
    {
        info cur=info(a[i]-a[i-1], 1);
        while (!A.empty()&&cur<A.back()) cur.x+=A.back().x, cur.y+=A.back().y, A.pop_back();
        A.push_back(cur); 
    }
    for (int i=2; i<=w; i++)
    {
        info cur=info(b[i]-b[i-1], 1);
        while (!B.empty()&&cur<B.back()) cur.x+=B.back().x, cur.y+=B.back().y, B.pop_back();
        B.push_back(cur); 
    }
    ca=a[1], cb=b[1];
    while (!A.empty()||!B.empty())
    {
        if (B.empty()||(!A.empty()&&A.front()<B.front())) res+=A.front().y*cb, ca+=A.front().x, A.pop_front();
        else res+=B.front().y*ca, cb+=B.front().x, B.pop_front();
    }
    cout<<res;
}

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