Submission #756475

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
756475	2023-06-11T17:42:09 Z	Olympia	Schools (IZhO13_school)	C++17	25 / 100	2000 ms	5472 KB

school

#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;
    		}
    		//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;
    		}
    	}
    	sort(music.begin(), music.end(), comp);
    	//reverse(music.begin(), music.end());
    	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

school.cpp: In function 'int64_t val()':
school.cpp:18:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |  for (int i = 0; i < music.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~
school.cpp:21:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  for (int i = 0; i < sports.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~
school.cpp: In function 'int64_t solve(int, int)':
school.cpp:33:23: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   33 |      if (music.size() < M or sports.size() < S) {
      |          ~~~~~~~~~~~~~^~~
school.cpp:33:44: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   33 |      if (music.size() < M or sports.size() < S) {
      |                              ~~~~~~~~~~~~~~^~~
school.cpp:34:24: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   34 |       if (music.size() < M) {
      |           ~~~~~~~~~~~~~^~~
school.cpp:36:32: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   36 |       } else if (sports.size() < S) {
      |                  ~~~~~~~~~~~~~~^~~
school.cpp:41:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |       for (int i = 0; i < music.size(); i++) {
      |                       ~~^~~~~~~~~~~~~~
school.cpp:47:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |       for (int i = 0; i < sports.size(); i++) {
      |                       ~~^~~~~~~~~~~~~~~
school.cpp:57:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |       for (int i = 0; i < music.size(); i++) {
      |                       ~~^~~~~~~~~~~~~~
school.cpp:65:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |       for (int i = 0; i < sports.size(); i++) {
      |                       ~~^~~~~~~~~~~~~~~

Subtask #1

25.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Incorrect	1 ms	212 KB	Output isn't correct
5	Correct	1 ms	284 KB	Output is correct
6	Incorrect	1 ms	212 KB	Output isn't correct
7	Execution timed out	2072 ms	408 KB	Time limit exceeded
8	Correct	749 ms	500 KB	Output is correct
9	Execution timed out	2044 ms	560 KB	Time limit exceeded
10	Execution timed out	2073 ms	500 KB	Time limit exceeded
11	Execution timed out	2065 ms	504 KB	Time limit exceeded
12	Execution timed out	2032 ms	604 KB	Time limit exceeded
13	Execution timed out	2061 ms	1228 KB	Time limit exceeded
14	Execution timed out	2023 ms	1780 KB	Time limit exceeded
15	Execution timed out	2078 ms	3028 KB	Time limit exceeded
16	Execution timed out	2072 ms	3344 KB	Time limit exceeded
17	Execution timed out	2069 ms	3912 KB	Time limit exceeded
18	Execution timed out	2053 ms	4300 KB	Time limit exceeded
19	Execution timed out	2063 ms	4752 KB	Time limit exceeded
20	Execution timed out	2066 ms	5472 KB	Time limit exceeded