oj.uz

답안 #756496

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
756496 2023-06-11T18:01:10 Z Olympia 학교 설립 (IZhO13_school) C++17
60 / 100
 2000 ms 25760 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;
bool comp (pair<int64_t, int64_t> p1, pair<int64_t, int64_t> p2) {
	return (p1.first - p1.second < p2.first - p2.second);
}
multiset<int64_t> music;
multiset<int64_t> sport;
vector<pair<int64_t, int64_t>> vec;
void remove_music (pair<int64_t,int64_t> p) {
	music.erase(music.find(p.first));
}
void add_sport (pair<int64_t,int64_t> p) {
	sport.insert(p.second);
}
void add_music (pair<int64_t,int64_t> p) {
	music.insert(p.first);
}
int64_t get_max(multiset<int64_t>& ms, int k) {
	if (ms.size() < k) {
		return -1e17;
	}
	vector<int64_t> vec;
	for (auto& i: ms) {
		vec.push_back(i);
	}
	int64_t ans = 0;
	while (k != 0) {
		ans += vec.back();
		vec.pop_back();
		k--;
	}
	return ans;
}
int64_t solve (int M, int S) {
	multiset<pair<int,int>> ms;
	if (M == 0) {
		int64_t ans = 0;
		for (auto& p: vec) {
			ans += p.second;
		}
		return ans;
	}
	if (S == 0) {
		int64_t ans = 0;
		for (auto& p: vec) {
			ans += p.first;
		}
		return ans;
	}
	sort(vec.begin(), vec.end(), comp);
	for (int i = 0; i < vec.size(); i++) {
		add_music(vec[i]);
	}
	int64_t ans = 0;
	for (int i = 0; i < vec.size(); i++) {
		remove_music(vec[i]);
		add_sport(vec[i]);
		ans = max(get_max(music, M) + get_max(sport, S), ans);
	}
	return ans;
}
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 get_max(std::multiset<long int>&, int)':
school.cpp:30:16: warning: comparison of integer expressions of different signedness: 'std::multiset<long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   30 |  if (ms.size() < k) {
      |      ~~~~~~~~~~^~~
school.cpp: In function 'int64_t solve(int, int)':
school.cpp:62: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]
   62 |  for (int i = 0; i < vec.size(); i++) {
      |                  ~~^~~~~~~~~~~~
school.cpp:66: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]
   66 |  for (int i = 0; i < vec.size(); i++) {
      |                  ~~^~~~~~~~~~~~

Subtask #1
60.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 197 ms 676 KB Output is correct
8 Correct 111 ms 596 KB Output is correct
9 Correct 154 ms 692 KB Output is correct
10 Correct 155 ms 700 KB Output is correct
11 Correct 186 ms 724 KB Output is correct
12 Correct 184 ms 724 KB Output is correct
13 Execution timed out 2078 ms 3792 KB Time limit exceeded
14 Execution timed out 2060 ms 7252 KB Time limit exceeded
15 Execution timed out 2032 ms 13928 KB Time limit exceeded
16 Execution timed out 2065 ms 15228 KB Time limit exceeded
17 Execution timed out 2073 ms 18048 KB Time limit exceeded
18 Execution timed out 2074 ms 19520 KB Time limit exceeded
19 Execution timed out 2041 ms 20876 KB Time limit exceeded
20 Execution timed out 2068 ms 25760 KB Time limit exceeded