oj.uz

Submission #635092

# Submission time Handle Problem Language Result Execution time Memory
635092 2022-08-25T12:07:15 Z pragmatist Schools (IZhO13_school) C++17
30 / 100
 2000 ms 262144 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 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];

void solve() {
	cin >> n >> m >> s;
	for(int i = 1; i <= n; ++i) cin >> a[i] >> b[i];
	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;  
}
 
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
30.0 / 100.0

# 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 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Execution timed out 2087 ms 5588 KB Time limit exceeded
8 Execution timed out 2063 ms 7252 KB Time limit exceeded
9 Execution timed out 2061 ms 29396 KB Time limit exceeded
10 Execution timed out 2087 ms 9172 KB Time limit exceeded
11 Execution timed out 2064 ms 28372 KB Time limit exceeded
12 Execution timed out 2071 ms 5588 KB Time limit exceeded
13 Runtime error 122 ms 262144 KB Execution killed with signal 9
14 Runtime error 126 ms 262144 KB Execution killed with signal 9
15 Execution timed out 2077 ms 6208 KB Time limit exceeded
16 Runtime error 122 ms 262144 KB Execution killed with signal 9
17 Runtime error 134 ms 262144 KB Execution killed with signal 9
18 Runtime error 133 ms 262144 KB Execution killed with signal 9
19 Runtime error 138 ms 262144 KB Execution killed with signal 9
20 Runtime error 135 ms 262144 KB Execution killed with signal 9