Submission #747457

#	Time	Username	Problem	Language	Result	Execution time	Memory
747457		Can_I_Put_ma_ballz	Art Exhibition (JOI18_art)	C++17	0 / 100	0 ms	212 KiB

art

#include <iomanip>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <map>
#include <climits>
#include <limits>


#define endl '\n'

typedef unsigned long long int u64;
typedef long long int i64;
typedef unsigned int u32;
typedef int i32;
typedef unsigned short u16;
typedef short i16;

using namespace std;


vector<pair<i64, i64>> get_max_r(const vector<i32>& arr) {
    vector<pair<i64, i64>> maxR(arr.size());
    vector<pair<i64, i64>> stack;


    for (int i = (int) arr.size() - 1; i >= 0; i--) {
        if(stack.empty()) {
            maxR[i].first = -1;
            maxR[i].second = (i64) arr.size();
        } else if (stack.back().first >= arr[i]) {
            maxR[i].first = stack.back().first;
            maxR[i].second = stack.back().second;
        } else {
            while (!stack.empty() && stack.back().first < arr[i]) {
                stack.pop_back();
            }

            if (!stack.empty()) {
                maxR[i].first = stack.back().first;
                maxR[i].second = stack.back().second;
            } else {
                maxR[i].first = -1;
                maxR[i].second = (i64) arr.size();
            }
        }

        stack.emplace_back(arr[i], i);
    }

    return maxR;
}

vector<pair<i64, i64>> get_max_l(const vector<i32>& arr) {
    vector<pair<i64, i64>> maxL(arr.size());
    vector<pair<i64, i64>> stack;


    for (int i = 0; i < arr.size(); i++) {
        if (stack.empty()) {
            maxL[i].first = -1;
            maxL[i].second = -1;
        } else if (stack.back().first > arr[i]) {
            maxL[i].first = stack.back().first;
            maxL[i].second = stack.back().second;
        } else {
            while (!stack.empty() && stack.back().first <= arr[i]) {
                stack.pop_back();
            }

            if (!stack.empty()) {
                maxL[i].first = stack.back().first;
                maxL[i].second = stack.back().second;
            } else {
                maxL[i].first = -1;
                maxL[i].second = -1;
            }
        }

        stack.emplace_back(pair<int, int>(arr[i], i));
    }

    return maxL;
}

int main() {
    ios::sync_with_stdio(NULL);cin.tie(nullptr);cout.tie(nullptr);

    i64 n;
    cin>>n;


    i64 sum = 0;
    vector<pair<i64, i64>> arr(n);
    for (auto& i:arr) {
        cin>>i.first>>i.second;
        sum += i.second;
    }

    sort(arr.begin(), arr.end(), [](auto x, auto y) {
        if (x.first == y.first) {
            return x.second > y.second;
        }
        return x.first < y.first;
    });


    size_t l = 0, r = n-1;
    i64 ans = LLONG_MIN;


    while (l <= r) {
        ans = max(ans, sum-(arr[r].first-arr[l].first));

        if (l != r) {
            i64 ml,mr;
            ml=(sum-arr[l].second)-(arr[r].first-arr[l+1].first);
            mr=(sum-arr[r].second)-(arr[r-1].first-arr[l].first);
            if (ml > mr) {
                sum -= arr[l].second;
                l++;
            } else {
                sum -= arr[r].second;
                r--;
            }
        } else {
            break;
        }
    }

    cout << ans << endl;


    return 0;
}

Compilation message (stderr)

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

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 50