Submission #559676

#	Time	Username	Problem	Language	Result	Execution time	Memory
559676		Trunkty	San (COCI17_san)	C++14	24 / 120	524 ms	10620 KiB

san

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;

#define DEBUG
#ifdef DEBUG
  #define debug(x) cout << #x << ": " << x << endl
#else
  #define debug(x)
#endif

ll n,p,m,ans;
ll arr[45],cost[45];
vector<ll> poss[45];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> p;
	for(ll i=1;i<=n;i++){
		cin >> arr[i] >> cost[i];
	}
	m = n/2;
	for(ll i=1;i<=m;i++){
		poss[i].push_back(cost[i]);
		for(ll j=1;j<i;j++){
			if(arr[i]>=arr[j]){
				for(ll k:poss[j]){
					poss[i].push_back(k+cost[i]);
				}
			}
		}
	}
	for(ll i=m+1;i<=n;i++){
		poss[i].push_back(cost[i]);
		for(ll j=m+1;j<i;j++){
			if(arr[i]>=arr[j]){
				for(ll k:poss[j]){
					poss[i].push_back(k+cost[i]);
				}
			}
		}
	}
	for(ll i=m+1;i<=n;i++){
		deque<ll> dq;
		for(ll j=1;j<=m;j++){
			if(arr[i]>=arr[j]){
				for(ll k:poss[j]){
					dq.push_back(k);
				}
			}
		}
		sort(dq.begin(),dq.end());
		sort(poss[i].begin(),poss[i].end(),greater<ll>());
		for(ll j:poss[i]){
			while(dq.size()>0 and dq.front()+j<p){
				dq.pop_front();
			}
			ll siz = dq.size();
			ans += siz;
		}
	}
	for(ll i=1;i<=n;i++){
		for(ll j:poss[i]){
			if(j>=p){
				ans++;
			}
		}
	}
	cout << ans << "\n";
	return 0;
}

• Subtask 1: 0 / 24
• Subtask 2: 24 / 24
• Subtask 3: 0 / 24
• Subtask 4: 0 / 24
• Subtask 5: 0 / 24