oj.uz

Submission #559672

# Submission time Handle Problem Language Result Execution time Memory
559672 2022-05-10T11:18:01 Z Trunkty San (COCI17_san) C++14
24 / 120
 557 ms 10680 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;
		dq.push_back(0);
		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();
			}
			ans += dq.size();
		}
	}
	for(ll i=1;i<=m;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 328 KB Output is correct
2 Incorrect 1 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 324 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #3
0 / 24.0

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

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 66 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 557 ms 10680 KB Output isn't correct
2 Halted 0 ms 0 KB -