# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
756485 | Olympia | Schools (IZhO13_school) | C++17 | 2072 ms | 5236 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <vector>
#include <iostream>
#include <cassert>
#include <random>
#include <cmath>
#include <map>
#include <algorithm>
#include <bitset>
#include <random>
#include <queue>
#include <set>
#include <stack>
using namespace std;
vector<pair<int64_t,int64_t>> music, sports;
vector<pair<int64_t,int64_t>> vec;
int64_t val () {
int64_t ans = 0;
for (int i = 0; i < music.size(); i++) {
ans += music[i].first;
}
for (int i = 0; i < sports.size(); i++) {
ans += sports[i].second;
}
return ans;
}
bool comp (pair<int64_t, int64_t> p1, pair<int64_t, int64_t> p2) {
return (p1.first - p1.second < p2.first - p2.second);
}
int64_t solve (int M, int S) {
music.clear(), sports.clear();
random_shuffle(vec.begin(), vec.end());
for (auto& value: vec) {
if (music.size() < M or sports.size() < S) {
if (music.size() < M) {
music.push_back(value);
} else if (sports.size() < S) {
sports.push_back(value);
}
} else {
int64_t mx = 0;
for (int i = 0; i < music.size(); i++) {
auto m = music[i];
music[i] = value;
mx = max(mx, val());
music[i] = m;
}
for (int i = 0; i < sports.size(); i++) {
auto s = sports[i];
sports[i] = value;
mx = max(mx, val());
sports[i] = s;
}
if (mx < val()) {
continue;
}
bool broken = false;
for (int i = 0; i < music.size(); i++) {
auto m = music[i];
music[i] = value;
if (val() == mx) {
broken = true;
break;
}
music[i] = m;
}
if (broken) continue;
for (int i = 0; i < sports.size(); i++) {
auto s = sports[i];
sports[i] = value;
if (val() == mx) {
break;
}
sports[i] = s;
}
}
sort(music.begin(), music.end(), comp);
sort(sports.begin(), sports.end(), comp);
reverse(sports.begin(), sports.end());
if (!sports.empty() and !music.empty() and sports[0].first + music[0].second > sports[0].second + music[0].first) {
swap(sports[0], music[0]);
}
}
return val();
}
int main () {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, M, S;
cin >> N >> M >> S;
vec.resize(N);
for (int i = 0; i < N; i++) {
cin >> vec[i].first >> vec[i].second;
}
cout << solve(M, S);
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |