Submission #1221552

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221552		giorgi123glm	Just Long Neckties (JOI20_ho_t1)	C++20	100 / 100	79 ms	10056 KiB

ho_t1

#include <bitset>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <array>
using namespace std;

#define int long long

signed main () {
    ios::sync_with_stdio (false);
    cin.tie (0);
    cout.tie (0);

    int N = 0;
    cin >> N;

    vector <pair <int, int> > ties (N + 2);
    for (int i = 1; i <= N + 1; i++) {
        cin >> ties[i].first;
        ties[i].second = i;
    }

    vector <int> odd (N + 1);
    for (int i = 1; i <= N; i++)
        cin >> odd[i];

    sort (ties.begin() + 1, ties.end());
    sort (odd.begin() + 1, odd.end());

    vector <int> pref (N + 1);
    for (int i = 1; i <= N; i++)
        pref[i] = max (pref[i - 1], max (ties[i].first - odd[i], 0ll));

    vector <int> ans (N + 2);
    int curans = 0;
    for (int i = N + 1; i >= 1; i--) {
        ans[ties[i].second] = max (pref[i - 1], curans);
        curans = max (curans, max (ties[i].first - odd[i - 1], 0ll));
    }

    for (int i = 1; i <= N + 1; i++)
        cout << ans[i] << ' ';
}

• Subtask 1: 1 / 1
• Subtask 2: 8 / 8
• Subtask 3: 91 / 91