Submission #1247595

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247595		leinad2	Sightseeing in Kyoto (JOI22_kyoto)	C++20	100 / 100	21 ms	10488 KiB

kyoto

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, m, i, j, k, a, b, A[500010], B[500010];
long double ans;
vector<int>V1, V2;
vector<long double>f(vector<int>V)
{
    vector<pair<int, int> >hull;
    for(auto p:V)
    {
        int x=p, h=1;
        while(hull.size())
        {
            if(x*hull.back().second<=h*hull.back().first)
            {
                x+=hull.back().first;
                h+=hull.back().second;
                hull.pop_back();
            }
            else break;
        }
        hull.push_back({x, h});
    }
    vector<long double>ans;
    for(auto p:hull)
    {
        for(int i=0;i<p.second;i++)ans.push_back((long double)(p.first)/p.second);
    }
    return ans;
}
main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>m;n--;m--;
    for(i=0;i<=n;i++)cin>>A[i];
    for(i=0;i<=m;i++)cin>>B[i];
    ans=A[n]*m+B[0]*n;
    for(i=n-1;i>=0;i--)V1.push_back(A[i]-A[i+1]);
    for(i=0;i<m;i++)V2.push_back(B[i+1]-B[i]);
    vector<long double>R=f(V1), C=f(V2);
    //cout<<ans<<endl;for(auto p:R)cout<<p<<" ";cout<<endl;for(auto p:C)cout<<p<<" ";cout<<endl;
    long double sum=0;
    int pt=0;
    for(i=(int)C.size()-1;i>=0;i--)
    {
        while(pt<R.size()&&R[pt]+C[i]<0)
        {
            sum+=R[pt];
            pt++;
        }
        ans+=(C[i]*pt+sum);
    }
    int x=round(ans);
    cout<<x;
}

Compilation message (stderr)

kyoto.cpp:32:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   32 | main()
      | ^~~~

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