Submission #821757

#	Time	Username	Problem	Language	Result	Execution time	Memory
821757		danikoynov	Sightseeing in Kyoto (JOI22_kyoto)	C++14	0 / 100	2 ms	980 KiB

kyoto

#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 = 1e3 + 10;
const ll inf = 1e18;
int h, w;
ll a[maxn], b[maxn], dp[maxn];

struct slope
{
    int idx, type;
    ll num, den;

    slope(int _idx = 0, int _type = 0, ll _num = 0, ll _den = 0)
    {
        idx = _idx;
        type = _type;
        num = _num;
        den = _den;
    }
    bool operator < (const slope &s) const
    {
        return num * s.den > s.num * den;
    }
};

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];

    set < int > active_row, active_col;
    multiset < slope > dif;
    for (int i = 2; i <= h; i ++)
    {
        active_row.insert(i);
        slope cur(i, 0, a[i] - a[i - 1], 1);
        dif.insert(cur);
    }

    for (int i = 2; i <= w; i ++)
    {
        active_col.insert(i);
        slope cur(i, 1, b[i] - b[i - 1], 1);
        dif.insert(cur);
    }

    ll ans = 0;
    while(!dif.empty())
    {
        slope cur = *dif.begin();
        dif.erase(dif.find(cur));

        ///cout << "step " << cur.idx << " " << cur.type << " " << cur.num << " " << cur.den << endl;

        if (cur.type == 0)
        {
            set < int > :: iterator it = active_row.find(cur.idx);

            if (next(it) == active_row.end())
            {
                int last = 1, bef = 1;
                if (it != active_row.begin())
                    bef = *prev(it);
                if (active_col.size() > 0)
                    last = *active_col.rbegin();

                ans = ans + (ll)(*it - bef) * b[last];
                ///cout << "ans " << ans << " " << *it - bef << " " << endl;
            }
            else
            {
                int nxt = *next(it);
                slope sl(nxt, 0, a[nxt] - a[cur.idx], nxt - cur.idx);
                dif.erase(dif.find(sl));
                int bef = 1;
                if (it != active_row.begin())
                    bef = *prev(it);
                sl = slope(nxt, 0, a[nxt] - a[bef], nxt - bef);
                dif.insert(sl);
            }

            active_row.erase(it);
        }
        else
        {
            set < int > :: iterator it = active_col.find(cur.idx);

            if (next(it) == active_col.end())
            {
                int last = 1, bef = 1;
                if (it != active_col.begin())
                    bef = *prev(it);
                if (active_row.size() > 0)
                    last = *active_row.rbegin();

                ans = ans + (ll)(*it - bef) * a[last];

            }
            else
            {
                int nxt = *next(it);
                slope sl(nxt, 1, b[nxt] - b[cur.idx], nxt - cur.idx);
                dif.erase(dif.find(sl));
                int bef = 1;
                if (it != active_col.begin())
                    bef = *prev(it);
                sl = slope(nxt, 1, b[nxt] - b[bef], nxt - bef);
                dif.insert(sl);
            }

            active_col.erase(it);
        }
    }

    cout << ans << endl;
}

int main()
{
    speed();
    solve();
    return 0;
}
/**
8 9
3 8 1 11 15 23 6 7
18 9 2 5 14 8 6 30 17
*/

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