| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 756398 | Olympia | Schools (IZhO13_school) | C++17 | 2076 ms | 7316 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 + p2.first < p1.second + 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;
}
//cout << "GET " << mx << endl;
if (mx < val()) {
continue;
}
for (int i = 0; i < music.size(); i++) {
auto m = music[i];
music[i] = value;
if (val() == mx) {
continue;
}
music[i] = m;
}
for (int i = 0; i < sports.size(); i++) {
auto s = sports[i];
sports[i] = value;
if (val() == mx) {
continue;
}
sports[i] = s;
}
}
for (int i = 0; i < music.size(); i++) {
for (int j = 0; j < sports.size(); j++) {
int64_t orig_val = val();
swap(music[i], sports[j]);
int64_t new_val = val();
if (new_val < orig_val) {
swap(music[i], sports[j]);
}
}
}
}
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;
}
int T = 20;
int64_t mx = 0;
while (T--) {
mx = max(mx, solve(M, S));
}
cout << mx;
}
Compilation message (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||