제출 #1358748

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1358748		skuru	Art Exhibition (JOI18_art)	C++20	50 / 100	1096 ms	12124 KiB

art

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define by(x) [](const auto& a, const auto& b) { return a.x < b.x; }

template <typename T>
bool maximize(T& target, T candidate) {
    return target < candidate ? (target = candidate, true) : false;
}

struct Art {
    ll size, value;
} arts[505050];

ll valueSum[505050];

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

    int N;
    cin >> N;

    for (int i = 1; i <= N; i++) {
        auto& [size, value] = arts[i];
        cin >> size >> value;
    }

    sort(arts + 1, arts + N + 1, by(size));
    for (int i = 1; i <= N; i++) {
        valueSum[i] = valueSum[i - 1] + arts[i].value;
    }

    ll answer = 0;
    for (int i = 1; i <= N; i++) {
        for (int j = i; j <= N; j++) {
            ll sum = valueSum[j] - valueSum[i - 1];
            maximize(answer, sum - (arts[j].size - arts[i].size));
        }
    }

    cout << answer;

    return 0;
}

• 서브태스크 1: 10 / 10
• 서브태스크 2: 20 / 20
• 서브태스크 3: 20 / 20
• 서브태스크 4: 0 / 50