oj.uz

Submission #743458

# Submission time Handle Problem Language Result Execution time Memory
743458 2023-05-17T11:56:41 Z NintsiChkhaidze Ice Hockey World Championship (CEOI15_bobek) C++17
100 / 100
 311 ms 20840 KB 
#include <bits/stdc++.h>
#define ll long long
#define s second
#define pb push_back
#define f first
#define int ll 
using namespace std;
 
const int N = 45;
int a[N],b[N];
vector <int> v1,v2;

signed main (){
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
    
    int n,lim;
	cin>>n>>lim;
	
	for (int i =1; i<=n;i++){
		if (i > n/2) cin>>b[i - n/2];
		else cin>>a[i];
	}
	int m1 = n/2,m2 = n - m1;
	for (int i = 1; i < (1<<m1); i++){
		int cost=0;
		for (int j = 1; j <= m1; j++){
			if ((i & (1<<(j - 1)))) {
				cost += a[j];
			}
		}
		if (cost <= lim) v1.pb(cost);
	}
	
	for (int i = 1; i < (1<<m2); i++){
		int cost=0;
		for (int j = 1; j <= m2; j++){
			if ((i & (1<<(j - 1)))) {
				cost += b[j];
			}
		}
		if (cost <= lim) v2.pb(cost);
	}
	
	sort(v1.begin(),v1.end());
	sort(v2.begin(),v2.end());
	
	int ans = 1 + v1.size() + v2.size(),r=-1;
	for (int i = v1.size()-1; i >= 0; i--){
		while (r + 1 < v2.size() && v1[i] + v2[r + 1] <= lim) ++r;
		ans += r + 1;
	}
	cout<<ans;
}

/*
5 1000
100 1500 500 500 1000
*/

Compilation message

bobek.cpp: In function 'int main()':
bobek.cpp:49:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   while (r + 1 < v2.size() && v1[i] + v2[r + 1] <= lim) ++r;
      |          ~~~~~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.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
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 1968 KB Output is correct
2 Correct 78 ms 5404 KB Output is correct
3 Correct 311 ms 20724 KB Output is correct
4 Correct 72 ms 5416 KB Output is correct
5 Correct 12 ms 1604 KB Output is correct
6 Correct 8 ms 856 KB Output is correct
7 Correct 7 ms 320 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 2780 KB Output is correct
2 Correct 27 ms 2008 KB Output is correct
3 Correct 124 ms 10568 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 6 ms 984 KB Output is correct
6 Correct 16 ms 1600 KB Output is correct
7 Correct 7 ms 320 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 3496 KB Output is correct
2 Correct 107 ms 6556 KB Output is correct
3 Correct 109 ms 6608 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 71 ms 6520 KB Output is correct
6 Correct 257 ms 20840 KB Output is correct
7 Correct 44 ms 300 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 12716 KB Output is correct
2 Correct 25 ms 2008 KB Output is correct
3 Correct 9 ms 856 KB Output is correct
4 Correct 1 ms 316 KB Output is correct
5 Correct 7 ms 984 KB Output is correct
6 Correct 217 ms 12868 KB Output is correct
7 Correct 7 ms 320 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 2008 KB Output is correct
2 Correct 72 ms 5440 KB Output is correct
3 Correct 9 ms 984 KB Output is correct
4 Correct 9 ms 856 KB Output is correct
5 Correct 84 ms 6580 KB Output is correct
6 Correct 25 ms 2008 KB Output is correct
7 Correct 118 ms 212 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 304 ms 20760 KB Output is correct
2 Correct 28 ms 1972 KB Output is correct
3 Correct 9 ms 964 KB Output is correct
4 Correct 303 ms 20820 KB Output is correct
5 Correct 107 ms 10532 KB Output is correct
6 Correct 17 ms 1596 KB Output is correct
7 Correct 15 ms 316 KB Output is correct