Submission #849508

#	Time	Username	Problem	Language	Result	Execution time	Memory
849508		danikoynov	Sightseeing in Kyoto (JOI22_kyoto)	C++14	100 / 100	65 ms	10052 KiB

kyoto

/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}


const int maxn = 1e5 + 10;

struct point
{
    ll x, y;

    point(ll _x = 0, ll _y = 0)
    {
        x = _x;
        y = _y;
    }
};

ll signed_area(point A, point B, point C)
{
    ll area = (B.x - A.x) * (B.y + A.y) +
              (C.x - B.x) * (C.y + B.y) +
              (A.x - C.x) * (A.y + C.y);
    return area; /// area is multiplied by 2
}


int orientation(point A, point B, point C)
{
    ll area = signed_area(A, B, C);
    if (area > 0)
        return 1; /// clockwise
    if (area < 0)
        return -1; /// anticlockwise
    return 0; /// collinear
}

int h, w;
ll a[maxn], b[maxn];

vector < point > lower_hull(vector < point > v)
{
    vector < point > res;
    for (int i = 0; i < v.size(); i ++)
    {
        while(res.size() > 1 && orientation(res[res.size() - 2], res.back(), v[i]) >= 0)
            res.pop_back();
        res.push_back(v[i]);
    }
    return res;
}

void print_vector(vector < point > vec) /// debug
{
    for (point p : vec)
        cout << p.x << " ";
    cout << endl;
}

void solve()
{
    cin >> h >> w;
    for (int i = 1; i <= h; i ++)
        cin >> a[i];
    for (int i = 1; i <= w; i ++)
        cin >> b[i];

    vector < point > row, col;

    for (int i = 1; i <= h; i ++)
    {
        row.push_back(point(i, a[i]));
    }

    for (int i = 1; i <= w; i ++)
    {
        col.push_back(point(i, b[i]));
    }

    row = lower_hull(row);
    col = lower_hull(col);

    /// print hull
    /**cout << "row hull: ";
    print_vector(row);
        cout << "col hull: ";
    print_vector(col);*/
    ///exit(0);
    ll ans = 0;
    while(true)
    {
        if (row.size() == 1 && col.size() == 1)
            break;

        if (row.size() == 1)
        {
            point cur = col.back();
            col.pop_back();
            ans = ans + (cur.x - col.back().x) * row.back().y;
        }
        else if (col.size() == 1)
        {
            point cur = row.back();
            row.pop_back();
            ans = ans + (cur.x - row.back().x) * col.back().y;
        }
        else
        {
            /// row slope = (row[n].y - row[n - 1].y) / (row[n].x - row[n - 1].x)
            /// col slope = (col[m].y - col[m - 1].y) / (col[m].x - col[m - 1].x)
            ///if (row_slope > col_slope)
            int rs = row.size(), cs = col.size();
            ///cout << "row slope "<< row[rs - 1].y - row[rs - 2].y << " " << row[rs - 1].x - row[rs - 2].x << endl;
            if ((row[rs - 1].y - row[rs - 2].y) * (col[cs - 1].x - col[cs - 2].x) <
                    (col[cs - 1].y - col[cs - 2].y) * (row[rs - 1].x - row[rs - 2].x))
            {

                point cur = col.back();
                col.pop_back();
                ans = ans + (cur.x - col.back().x) * row.back().y;
            }
            else
            {
                point cur = row.back();
                row.pop_back();
                ans = ans + (cur.x - row.back().x) * col.back().y;
            }
        }
    }

    cout << ans << endl;
}

int main()
{
    solve();
    return 0;
}

Compilation message (stderr)

kyoto.cpp: In function 'std::vector<point> lower_hull(std::vector<point>)':
kyoto.cpp:61:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for (int i = 0; i < v.size(); i ++)
      |                     ~~^~~~~~~~~~

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