제출 #1174983

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

kyoto

#include<bits/stdc++.h>

#define fi first
#define se second

#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define sz(v) (int)(v).size()

#define endl "\n"
#define dbg(x) "[" #x " = " << (x) << "]"

using namespace std;

template<class T> bool minimize(T& a, T b){
    if(a > b) return a = b, true;
    return false;
}

template<class T> bool maximize(T& a, T b){
    if(a < b) return a = b, true;
    return false;
}

typedef long long ll;

void fastIO(){
    ios_base::sync_with_stdio(NULL); cin.tie(0);
#ifdef LOCAL
    freopen("task.INP", "r", stdin);
    freopen("task.OUT", "w", stdout);
#endif
}

struct point{
    ll x, y;
    point() : x(0), y(0) {}
    point(ll x, ll y) : x(x), y(y) {}


};

ll cross(point a, point b){
    return a.x*b.y - a.y*b.x;
}

void vectorize(point& a, point b){
    a.x -= b.x;
    a.y -= b.y;
}

ll cross_product(point a, point b, point c){
    vectorize(b, a);
    vectorize(c, a);
    return cross(b, c);
}

void lower_hull_construction(vector<point>& a){
    vector<point> hull;

    for(auto e : a){
        while(sz(hull) > 1 && cross_product(hull[sz(hull)-2], e, hull.back()) >= 0) hull.pop_back();
        hull.push_back(e);
    }

    swap(a, hull);
    return;
}

signed main(){
    fastIO();

    int H, W; cin >> H >> W;

    vector<point> a, b;

    for(int i = 1; i <= H; i++){
        int x; cin >> x;
        a.push_back(point(i, x));
    }

    for(int i = 1; i <= W; i++){
        int x; cin >> x;
        b.push_back(point(i, x));
    }

    lower_hull_construction(a);
    lower_hull_construction(b);

    int i = 0, j = 0;
    ll answer = 0;

    while(i < sz(a) - 1 || j < sz(b) - 1){
        if(i + 1 == sz(a)){
            answer += 1LL*(b[j+1].x - b[j].x)*a[i].y;
            j++;
            continue;
        }

        if(j + 1 == sz(b)){
            answer += 1LL*(a[i+1].x - a[i].x)*b[j].y;
            i++;
            continue;
        }

        ll A = 1LL*(a[i].y - a[i+1].y)*(b[j+1].x - b[j].x);
        ll B = 1LL*(b[j].y - b[j+1].y)*(a[i+1].x - a[i].x);

        if(A > B){
            answer += 1LL*(a[i+1].x - a[i].x)*b[j].y;
            i++;
        }
        else{
            answer += 1LL*(b[j+1].x - b[j].x)*a[i].y;
            j++;
        }
    }

    cout << answer;
}

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