oj.uz

Submission #87694

# Submission time Handle Problem Language Result Execution time Memory
87694 2018-12-02T02:42:08 Z jasony123123 San (COCI17_san) C++11
96 / 120
 392 ms 66560 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
//using namespace __gnu_pbds;

#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define vsort(a) sort(a.begin(), a.end());
#define mp make_pair
#define v vector
#define sf scanf
#define pf printf

typedef long long ll;
typedef pair<int, int > pii;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
void io();

int N;
ll K;
int H[42];
ll G[42];
map<ll, ll> cnt[42];

v<int> adj[42];
int usage[42];

int main() {
	io();
	cin >> N >> K;
	FORE(i, 1, N) {
		cin >> H[i] >> G[i];
	}
	H[N + 1] = 1e9 + 1;
	cnt[N + 1][0] = 1;

	FORE(i, 0, N) {
		FOR(j, i + 1, N + 2) {
			if (H[i] <= H[j]) {
				adj[i].push_back(j);
				usage[j] += i + 1;
			}
		}
	}

	RFORE(i, N, 0) {
		for(int j : adj[i]){
			for (auto &entry : cnt[j]) {
				cnt[i][min(K, entry.first + G[i])] += entry.second;
			}
			usage[j] -= i + 1;
			if (usage[j] == 0)
				cnt[j].clear();
		}
	}

	cout << cnt[0][K] << "\n";
	return 0;
}


void io() {
#ifdef LOCAL_PROJECT
	freopen("input.in", "r", stdin);
	freopen("output.out","w",stdout);
#else
	// add i/o method of specific testing system
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
}

Subtask #1
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 532 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 6256 KB Output is correct
2 Correct 6 ms 6256 KB Output is correct

Subtask #3
24.0 / 24.0

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

Subtask #4
24.0 / 24.0

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

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 14080 KB Output is correct
2 Runtime error 392 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)