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
#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++) {
      |                       ~~^~~~~~~~~~~~~~~
# 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