Submission #1189233

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189233		Zakir060	Art Exhibition (JOI18_art)	C++20	100 / 100	118 ms	12260 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 {
    ll size; // Dəyişiklik: int -> ll (Bu, böyük ölçüləri saxlamaq üçündür)
    int value; // Dəyərlər int-ə sığır, amma istəsəniz bunu da ll edə bilərsiniz
};

// Müqayisə funksiyası indi ll size ilə işləyir
bool compareArtworks(const Artwork& a, const Artwork& b) {
    // Əgər ölçülər bərabərdirsə, ardıcıllığın fərqi yoxdur,
    // amma bəzən dəyərə görə azalan sırada çeşidləmək də olar (vacib deyil)
    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) {
        // Girişi birbaşa ll size və int value-yə oxuyuruq
        std::cin >> artworks[i].size >> artworks[i].value; // artworks[i].size artıq ll tipindədir
    }

    // Ə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 (cəm ll olmalıdır)
    std::vector<ll> prefix_value_sum(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        // artworks[i].value int olsa da, prefix_value_sum[i] ll olduğu üçün cəm avtomatik ll olur
        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
    for (int j = 0; j < n; ++j) {
        // artworks[j].size artıq ll olduğu üçün əlavə cast (tip çevirmə) lazım deyil
        ll current_prefix_term = 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ı hesablayırıq: (P[j+1] - A_j) + max(A_i - P_i)
        // artworks[j].size artıq ll olduğu üçün əlavə cast lazım deyil
        ll current_objective = (prefix_value_sum[j + 1] - artworks[j].size) + max_prefix_term;

        // Ü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: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 50 / 50