oj.uz

Submission #235149

# Submission time Handle Problem Language Result Execution time Memory
235149 2020-05-27T07:51:32 Z NONAME San (COCI17_san) C++17
120 / 120
 327 ms 384 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 4 ms 256 KB Output is correct
2 Correct 4 ms 256 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 256 KB Output is correct
2 Correct 4 ms 256 KB Output is correct

Subtask #3
24.0 / 24.0

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

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 256 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 384 KB Output is correct
2 Correct 327 ms 384 KB Output is correct