Submission #1009371

#TimeUsernameProblemLanguageResultExecution timeMemory
1009371bornagSchools (IZhO13_school)C++14
30 / 100
27 ms23604 KiB
#include <bits/stdc++.h>
using namespace std;

const int maxn = 750;

int n, m, s;
int mchild[maxn];
int schild[maxn];
int dp[maxn][maxn][maxn];

int sol = 0;

int main(){
	cin >> n >> m >> s;
	
	for(int i = 0; i < n; i++){
		cin >> mchild[i] >> schild[i];
	}
	
	for(int i = 1; i <= n; i++){
		for(int j = 0; j <= m; j++){
			for(int k = 0; k <= s; k++){
				if(k == 0 and j == 0) continue; 
				dp[i][j][k] = max(dp[i-1][j][k], dp[i][j][k]);
				
				int ssl = 0;
				if(k == 0) ssl = dp[i-1][j-1][k]+mchild[i-1];
				else if(j == 0) ssl = dp[i-1][j][k-1]+schild[i-1];
				else ssl = max(dp[i-1][j-1][k]+mchild[i-1], dp[i-1][j][k-1]+schild[i-1]);
				
				dp[i][j][k] = max(ssl, dp[i][j][k]);
			}
		}
		
		//cout << dp[i][1][1] << '\n';
	}
	
	cout << dp[n][m][s] << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...