oj.uz

답안 #635109

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
635109 2022-08-25T12:30:37 Z pragmatist 학교 설립 (IZhO13_school) C++17
35 / 100
 2000 ms 29524 KB 
#include<bits/stdc++.h>
 
#define ll long long
#define pb push_back
#define x first
#define y second
#define sz(v) (int)v.size()
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define ld long double              
#define nl "\n"

using namespace std;
using pii = pair<int, int>;
 
const int N = (int)3e5 + 7;
const int inf = (int)1e9 + 7;
const ll INF = (ll)1e18 + 7;
const int MOD = (int)1e9 + 7;
const int M = (int)5e4 + 7; 

int n, m, s, a[N], b[N];
bool used[N];

void solve() {
	cin >> n >> m >> s;
	vector<pair<pii, int> > v;
	for(int i = 1; i <= n; ++i) {
		cin >> a[i] >> b[i];
		v.pb({{a[i], -b[i]}, i});
	}
	if(n <= 5000) {
			ll dp[m + 1][s + 1], pd[m + 1][s + 1];
	for(int j = 0; j <= m; ++j) 
		for(int k = 0; k <= s; ++k)
			dp[j][k] = pd[j][k] = -INF;
	dp[0][0] = 0;
	for(int i = 1; i <= n; ++i) {
		for(int j = 0; j <= m; ++j) {
			for(int k = 0; k <= s; ++k) {
				pd[j][k] = max({dp[j][k], (j == 0 ? -INF : dp[j - 1][k]  + a[i]), (k == 0 ? -INF : dp[j][k - 1] + b[i])});
			}
		}
		for(int j = 0; j <= m; ++j) {
			for(int k = 0; k <= s; ++k) {
		    	dp[j][k] = pd[j][k];
				pd[j][k] = -INF;
			}
		}
		dp[0][0] = 0;
	}
	
	cout << dp[m][s] << nl;  
		return;
	}
	sort(rall(v));
	ll A = 0, B = 0;
	for(int i = 0; i < m; ++i) {
		A += v[i].x.x;
		used[v[i].y] = 1;
	}        
	v.clear();
	for(int i = 1; i <= n; ++i) {
		if(used[i]) continue;
		v.pb({{b[i], 0}, 0});
	}
	sort(rall(v));
	for(int i = 0; i < s; ++i)
		A += v[i].x.x;

	v.clear();
	memset(used, 0, sizeof(used));
	
	for(int i = 1; i <= n; ++i) {
		v.pb({{b[i], -a[i]}, i});
	}
	sort(rall(v));
	for(int i = 0; i < s; ++i) {
		B += v[i].x.x;
		used[v[i].y] = 1;
	}
	v.clear();
	for(int i = 1; i <= n; ++i) {
		if(used[i]) continue;
		v.pb({{a[i], 0}, 0});
	}
	sort(rall(v));
	for(int i = 0; i < m; ++i)
		B += v[i].x.x;

	cout << max(A, B) << nl;
}
 
int main() {
	ios_base::sync_with_stdio(NULL);
	cin.tie(0);
	cout.tie(0);
	int test = 1;
	//cin >> test;
	while(test--) {
		solve();
	}
	return 0;
}

Subtask #1
35.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Execution timed out 2081 ms 5844 KB Time limit exceeded
8 Execution timed out 2085 ms 7508 KB Time limit exceeded
9 Execution timed out 2078 ms 29524 KB Time limit exceeded
10 Execution timed out 2075 ms 9300 KB Time limit exceeded
11 Execution timed out 2082 ms 28500 KB Time limit exceeded
12 Execution timed out 2079 ms 5716 KB Time limit exceeded
13 Incorrect 16 ms 1488 KB Output isn't correct
14 Incorrect 42 ms 2508 KB Output isn't correct
15 Correct 87 ms 4588 KB Output is correct
16 Incorrect 81 ms 4536 KB Output isn't correct
17 Incorrect 102 ms 4952 KB Output isn't correct
18 Incorrect 111 ms 5332 KB Output isn't correct
19 Incorrect 132 ms 5780 KB Output isn't correct
20 Incorrect 148 ms 8596 KB Output isn't correct