oj.uz

Submission #197343

# Submission time Handle Problem Language Result Execution time Memory
197343 2020-01-20T12:58:40 Z nafis_shifat Ice Hockey World Championship (CEOI15_bobek) C++14
100 / 100
 589 ms 20944 KB 
#include<bits/stdc++.h>
#define pii pair<int,int>
#define ll long long
using namespace std;

vector<ll> v1;
vector<ll> v2;


ll a[45];

ll clc(int mask,int b,int e,ll m)
{
	ll cur=0;
	for(int i=b,j=1;i<=e;i++,j++)
	{
		if((mask>>(j-1))&1)
		{
			if(cur+a[i]>m)return -1;
			cur+=a[i];			
		}
	}
	return cur;
}
int main()
{
	int n;
	cin>>n;
	ll m;
	cin>>m;
	int m1=n/2;
	int m2=n-m1;





	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}



	for(int i=0;i<(1<<m1);i++)
	{
		ll c=clc(i,1,m1,m);
		if(c!=-1)v1.push_back(c);
	}


	for(int i=0;i<(1<<m2);i++)
	{
		ll c=clc(i,m1+1,n,m);
		if(c!=-1)v2.push_back(c);
	}
	

	sort(v2.begin(),v2.end());
	


	ll rs=0;



	for(int i=0;i<v1.size();i++)
	{
		ll cur=v1[i];
		ll r=m-cur;
		ll d=upper_bound(v2.begin(),v2.end(),r)-v2.begin();
	
		rs+=d;
		
		

	}

	cout<<rs<<endl;





	



	return 0;
}

Compilation message

bobek.cpp: In function 'int main()':
bobek.cpp:67:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<v1.size();i++)
              ~^~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 256 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 2044 KB Output is correct
2 Correct 122 ms 5456 KB Output is correct
3 Correct 589 ms 20944 KB Output is correct
4 Correct 128 ms 5780 KB Output is correct
5 Correct 20 ms 1692 KB Output is correct
6 Correct 15 ms 1012 KB Output is correct
7 Correct 3 ms 256 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 2924 KB Output is correct
2 Correct 42 ms 2076 KB Output is correct
3 Correct 248 ms 10600 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 10 ms 1024 KB Output is correct
6 Correct 20 ms 1648 KB Output is correct
7 Correct 3 ms 508 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 3564 KB Output is correct
2 Correct 173 ms 6680 KB Output is correct
3 Correct 179 ms 6624 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 102 ms 6756 KB Output is correct
6 Correct 324 ms 20788 KB Output is correct
7 Correct 6 ms 256 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 386 ms 12760 KB Output is correct
2 Correct 38 ms 2032 KB Output is correct
3 Correct 14 ms 1012 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 10 ms 1016 KB Output is correct
6 Correct 268 ms 12760 KB Output is correct
7 Correct 3 ms 256 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 2080 KB Output is correct
2 Correct 122 ms 5536 KB Output is correct
3 Correct 13 ms 1012 KB Output is correct
4 Correct 13 ms 884 KB Output is correct
5 Correct 114 ms 6688 KB Output is correct
6 Correct 31 ms 2028 KB Output is correct
7 Correct 12 ms 256 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 481 ms 20836 KB Output is correct
2 Correct 40 ms 2032 KB Output is correct
3 Correct 13 ms 1012 KB Output is correct
4 Correct 551 ms 20852 KB Output is correct
5 Correct 150 ms 10592 KB Output is correct
6 Correct 20 ms 1648 KB Output is correct
7 Correct 3 ms 256 KB Output is correct