oj.uz

답안 #756498

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
756498 2023-06-11T18:03:20 Z Olympia 학교 설립 (IZhO13_school) C++17
60 / 100
 2000 ms 22728 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++) {
		if (i <= S - 2) {
			add_sport(vec[i]);
		} else {
			add_music(vec[i]);
		}
	}
	int64_t ans = 0;
	for (int i = S - 1; 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:70:24: 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]
   70 |  for (int i = S - 1; i < vec.size(); i++) {
      |                      ~~^~~~~~~~~~~~

Subtask #1
60.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 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 160 ms 636 KB Output is correct
8 Correct 117 ms 596 KB Output is correct
9 Correct 133 ms 684 KB Output is correct
10 Correct 161 ms 724 KB Output is correct
11 Correct 76 ms 712 KB Output is correct
12 Correct 69 ms 712 KB Output is correct
13 Execution timed out 2081 ms 3608 KB Time limit exceeded
14 Execution timed out 2061 ms 6244 KB Time limit exceeded
15 Execution timed out 2073 ms 13644 KB Time limit exceeded
16 Execution timed out 2068 ms 15140 KB Time limit exceeded
17 Execution timed out 2069 ms 15968 KB Time limit exceeded
18 Execution timed out 2059 ms 18736 KB Time limit exceeded
19 Execution timed out 2070 ms 20000 KB Time limit exceeded
20 Execution timed out 2073 ms 22728 KB Time limit exceeded