oj.uz

Submission #635091

# Submission time Handle Problem Language Result Execution time Memory
635091 2022-08-25T12:04:27 Z pragmatist Schools (IZhO13_school) C++17
30 / 100
 2000 ms 40440 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];
ll dp[1001][1001], pd[1001][1001];

void solve() {
	cin >> n >> m >> s;
	for(int i = 1; i <= n; ++i) cin >> a[i] >> b[i];
	for(int j = 0; j <= m; ++j) 
		for(int k = 0; k <= m; ++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 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 3 ms 724 KB Output is correct
7 Execution timed out 2071 ms 4820 KB Time limit exceeded
8 Runtime error 27 ms 36992 KB Execution killed with signal 11
9 Runtime error 29 ms 36908 KB Execution killed with signal 11
10 Runtime error 29 ms 36968 KB Execution killed with signal 11
11 Execution timed out 2077 ms 8148 KB Time limit exceeded
12 Execution timed out 2081 ms 1776 KB Time limit exceeded
13 Runtime error 58 ms 37256 KB Execution killed with signal 11
14 Runtime error 44 ms 37796 KB Execution killed with signal 11
15 Execution timed out 2079 ms 4044 KB Time limit exceeded
16 Runtime error 69 ms 38924 KB Execution killed with signal 11
17 Runtime error 162 ms 39588 KB Execution killed with signal 11
18 Runtime error 134 ms 39792 KB Execution killed with signal 11
19 Runtime error 140 ms 39920 KB Execution killed with signal 11
20 Runtime error 156 ms 40440 KB Execution killed with signal 11