oj.uz

Submission #559676

# Submission time Handle Problem Language Result Execution time Memory
559676 2022-05-10T11:26:25 Z Trunkty San (COCI17_san) C++14
24 / 120
 524 ms 10620 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
24.0 / 24.0

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

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 1360 KB Output is correct
2 Incorrect 2 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 54 ms 2796 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 524 ms 10620 KB Output isn't correct
2 Halted 0 ms 0 KB -