Submission #1119818

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119818		onlk97	Sightseeing in Kyoto (JOI22_kyoto)	C++14	100 / 100	31 ms	5788 KiB

kyoto

#include <bits/stdc++.h>
#define int long long
#define x first
#define y second
#define pb push_back
using namespace std;
using pii=pair <int,int>;
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n,m;
    cin>>n>>m;
    int a[n+1],b[m+1];
    for (int i=1; i<=n; i++) cin>>a[i];
    for (int i=1; i<=m; i++) cin>>b[i];
    vector <pii> va,vb;
    va.pb({1,a[1]});
    for (int i=2; i<=n; i++){
        while (va.size()>1){
            int sz=va.size();
            if ((va[sz-1].y-va[sz-2].y)*(i-va[sz-1].x)>=(a[i]-va[sz-1].y)*(va[sz-1].x-va[sz-2].x)) va.pop_back();
            else break;
        }
        va.pb({i,a[i]});
    }
    vb.pb({1,b[1]});
    for (int i=2; i<=m; i++){
        while (vb.size()>1){
            int sz=vb.size();
            if ((vb[sz-1].y-vb[sz-2].y)*(i-vb[sz-1].x)>=(b[i]-vb[sz-1].y)*(vb[sz-1].x-vb[sz-2].x)) vb.pop_back();
            else break;
        }
        vb.pb({i,b[i]});
    }
    int ans=0,xp=0,yp=0;
    while (xp!=va.size()-1||yp!=vb.size()-1){
        int c;
        if (xp==va.size()-1) c=1;
        else if (yp==vb.size()-1) c=0;
        else if ((va[xp+1].y-va[xp].y)*(vb[yp+1].x-vb[yp].x)>=(vb[yp+1].y-vb[yp].y)*(va[xp+1].x-va[xp].x)) c=1;
        else c=0;
        if (c){
            ans+=va[xp].y*(vb[yp+1].x-vb[yp].x);
            yp++;
        } else {
            ans+=vb[yp].y*(va[xp+1].x-va[xp].x);
            xp++;
        }
    }
    cout<<ans<<'\n';
}

Compilation message (stderr)

kyoto.cpp: In function 'int main()':
kyoto.cpp:35:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     while (xp!=va.size()-1||yp!=vb.size()-1){
      |            ~~^~~~~~~~~~~~~
kyoto.cpp:35:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     while (xp!=va.size()-1||yp!=vb.size()-1){
      |                             ~~^~~~~~~~~~~~~
kyoto.cpp:37:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         if (xp==va.size()-1) c=1;
      |             ~~^~~~~~~~~~~~~
kyoto.cpp:38:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         else if (yp==vb.size()-1) c=0;
      |                  ~~^~~~~~~~~~~~~

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