Submission #1189233

#TimeUsernameProblemLanguageResultExecution timeMemory
1189233Zakir060Art Exhibition (JOI18_art)C++20
100 / 100
118 ms12260 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...