Submission #1189231

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189231		Zakir060	Art Exhibition (JOI18_art)	C++20	0 / 100	0 ms	320 KiB

art

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits> // LLONG_MIN üçün

// Rahatlıq üçün long long təyin edək
using ll = long long;

// Sənət əsərini təsvir edən struktur
struct Artwork {
    int size;
    int value;
};

// Ölçüyə görə müqayisə funksiyası
bool compareArtworks(const Artwork& a, const Artwork& b) {
    return a.size < b.size;
}

int main() {
    // Daha sürətli giriş/çıxış üçün
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n;

    std::vector<Artwork> artworks(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> artworks[i].size >> artworks[i].value;
    }

    // Əsərləri ölçülərinə görə çeşidləyirik
    std::sort(artworks.begin(), artworks.end(), compareArtworks);

    // Dəyərlərin (B_i) prefiks cəmlərini hesablayırıq
    std::vector<ll> prefix_value_sum(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        prefix_value_sum[i + 1] = prefix_value_sum[i] + artworks[i].value;
    }

    // Ümumi maksimum məqsəd dəyərini və indiyə qədərki max(A_i - P_i) dəyərini saxlamaq üçün
    ll max_total_objective = LLONG_MIN;
    ll max_prefix_term = LLONG_MIN; // max(A_i - P[i])

    // Çeşidlənmiş əsərlər üzərində dövr edirik.
    // Hər j iterasiyasında, j-ci əsəri potensial A_max olaraq qəbul edirik.
    for (int j = 0; j < n; ++j) {
        // i = j halı üçün (A_i - P_i) terminini hesablayırıq.
        // P[j] = prefix_value_sum[j] = 0-dan j-1-ə qədər dəyərlərin cəmidir.
        ll current_prefix_term = (ll)artworks[j].size - prefix_value_sum[j];

        // İndiyə qədər (i <= j) rast gəlinən ən böyük (A_i - P_i) dəyərini yeniləyirik.
        max_prefix_term = std::max(max_prefix_term, current_prefix_term);

        // Məqsəd funksiyasını (S - A_max + A_min) hesablayırıq.
        // S - A_max + A_min = (P[j+1] - A_j) + (A_i - P_i)
        // Sabit j üçün (P[j+1] - A_j) sabitdir, (A_i - P_i) terminini maksimallaşdırmalıyıq.
        // Bu maksimum dəyər `max_prefix_term`-də saxlanılır.
        ll current_objective = (prefix_value_sum[j + 1] - (ll)artworks[j].size) + max_prefix_term;

        // Bütün mümkün A_max seçimləri arasında tapılan ümumi maksimum məqsəd dəyərini yeniləyirik.
        max_total_objective = std::max(max_total_objective, current_objective);
    }

    // Yekun maksimum dəyəri çap edirik.
    std::cout << max_total_objective << std::endl;

    return 0;
}

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