oj.uz

Submission #821759

# Submission time Handle Problem Language Result Execution time Memory
821759 2023-08-11T15:45:43 Z danikoynov Sightseeing in Kyoto (JOI22_kyoto) C++14
0 / 100
 2 ms 992 KB 
#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;
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)
        {
            if (active_row.size() == 0)
                while(true);
            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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 2 ms 468 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Runtime error 2 ms 992 KB Execution killed with signal 6
17 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Runtime error 1 ms 852 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 2 ms 468 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Runtime error 2 ms 992 KB Execution killed with signal 6
17 Halted 0 ms 0 KB -