제출 #1362902

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1362902		ykilra	Sightseeing in Kyoto (JOI22_kyoto)	C++20	100 / 100	18 ms	2916 KiB

kyoto

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

const int N = 1e5+50;

int ans, a[N], b[N], h, w;
vector<int> ha, hb;
int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    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 = 1; i <= h; i++) {
        while (ha.size() >= 2) {
            int u = ha[ha.size()-2], v = ha[ha.size()-1];
            if ((a[v]-a[u])*(i-u) >= (a[i]-a[u])*(v-u)) { // lower hull
                ha.pop_back();
            }
            else break;
        }
        ha.push_back(i);
    }
    for (int i = 1; i <= w; i++) {
        while (hb.size() >= 2) {
            int u = hb[hb.size()-2], v = hb[hb.size()-1];
            if ((b[v]-b[u])*(i-u) >= (b[i]-b[u])*(v-u)) { // lower hull
                hb.pop_back();
            }
            else break;
        }
        hb.push_back(i);
    }

    int pa = 0, pb = 0, sa = ha.size(), sb = hb.size();
    while (pa+1 < sa || pb+1 < sb) {
        if (pa+1 == sa) { // goes right
            ans += a[ha[pa]] * (hb[pb+1]-hb[pb]);
            pb++;
        }
        else if (pb+1 == sb) {
            ans += b[hb[pb]] * (ha[pa+1]-ha[pa]);
            pa++;
        }
        else {
            int df = (a[ha[pa+1]]-a[ha[pa]])*(hb[pb+1]-hb[pb]);
            int rf = (b[hb[pb+1]]-b[hb[pb]])*(ha[pa+1]-ha[pa]);
            if (df <= rf) {
                ans += b[hb[pb]] * (ha[pa+1]-ha[pa]);
                pa++;
            }
            else {
                ans += a[ha[pa]] * (hb[pb+1]-hb[pb]);
                pb++;
            }
        }
    }
    cout << ans << '\n';
    return 0;
}

• 서브태스크 1: 10 / 10
• 서브태스크 2: 30 / 30
• 서브태스크 3: 60 / 60