oj.uz

Submission #797097

# Submission time Handle Problem Language Result Execution time Memory
797097 2023-07-29T06:38:44 Z Trisanu_Das San (COCI17_san) C++17
120 / 120
 249 ms 300 KB 
#include <bits/stdc++.h>
#define ft first
#define sd second
#define pb push_back
using namespace std;
typedef long long ll;
 
int n, h[40];
ll k, g[40], ans, f[40];
vector <int> gr[40];
 
void rec(int v, ll cr) {
	if (cr >= k) {
		ans += f[v];
		return;	
	}
	
	for (int u : gr[v])
		rec(u, cr + g[u]);	
}
 
int main() {
	cin >> n >> k;
	
	for (int i = 0; i < n; i++)
		cin >> h[i] >> g[i];
		
	for (int i = 0; i < n; i++)
	for (int j = i + 1; j < n; j++)
		if (h[i] <= h[j])
			gr[i].pb(j);
		
	for (int i = n - 1; i >= 0; i--) {
		f[i] = 1;
		
		for (int j : gr[i])
			f[i] += f[j];
	}
	
	for (int i = 0; i < n; i++)
		rec(i, g[i]);
		
	cout << ans;
}

Subtask #1
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB Output is correct
2 Correct 249 ms 284 KB Output is correct