oj.uz

Submission #37982

# Submission time Handle Problem Language Result Execution time Memory
37982 2017-12-29T21:03:48 Z wasyl San (COCI17_san) C++11
120 / 120
 293 ms 8504 KB 
#include <vector>
#include <iostream>
#include <algorithm>
#define d(...) __VA_ARGS__
#define all(x) (x).begin(), (x).end()
#define eb(...) emplace_back(__VA_ARGS__)
using namespace std;using ll=long long;
template<class t>using V = vector< t >;


ll res;
int n; ll ka;
V< int > tab;
V< int > ilo;
V< V< ll > > arr;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> ka;	
	tab.resize( n );
	ilo.resize( n );
	arr.resize( n );
	for ( int i = 0; i < n; ++i )
		cin >> tab[i] >> ilo[i];
	int pol = n / 2;
	for ( int i = 1; i < ( 1 << pol ); ++i )
	{
		bool fl = true;
		int currh = 0;
		ll sum = 0;
		int last = 0;
		for ( int k = 0; k < pol; ++k )
			if ( ( 1 << k ) & i )
			{
				last = k;
				if ( tab[k] < currh )
				{
					fl = false; break;
				}
				currh = tab[k];
				sum += ilo[k];			
			}
		if ( fl )
			arr[last].eb( sum );
	}
	int pop = pol;
	if ( pol * 2 < n ) ++pol;
	for ( int i = 1; i < ( 1 << pol ); ++i )
	{
		bool fl = true;
		int currh = 0;
		ll sum = 0;
		int first = 41;
		for ( int k = 0; k < pol; ++k )
			if ( ( 1 << k ) & i ) 
			{
				first = min( first, k + pop );
				if ( tab[k + pop] < currh )
				{
					fl = false; break;
				}
				currh = tab[k + pop];
				sum += ilo[k + pop];
			}
		if ( fl )
			arr[first].eb( sum );
	}

	for ( int i = 0; i < n; ++i )
		sort( all( arr[i] ) );
	
	for ( int i = 0; i < pop; ++i )
		for ( int k = pop; k < n; ++k )
		{
			if ( tab[i] <= tab[k] )
				for ( ll c : arr[k] )	
					res += arr[i].end() - lower_bound( all( arr[i] ),  ka - c );	
		}
//	for ( int i = 0; i < n; ++i )
//	{
//		cout << i << ": ";
//		for ( ll k : arr[i] )
//			cout << k << ' ';
//		cout << '\n';
//	}
	for ( int i = 0; i < n; ++i )
		res += arr[i].end() - lower_bound( all( arr[i] ), ka );
	cout << res << '\n';
}

Subtask #1
24.0 / 24.0

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

Subtask #2
24.0 / 24.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 2892 KB Output is correct
2 Correct 3 ms 2180 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 3924 KB Output is correct
2 Correct 19 ms 2448 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 8504 KB Output is correct
2 Correct 109 ms 4092 KB Output is correct