oj.uz

Submission #524904

# Submission time Handle Problem Language Result Execution time Memory
524904 2022-02-10T09:14:58 Z fuad27 Ice Hockey World Championship (CEOI15_bobek) C++17
100 / 100
 441 ms 8800 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
// using namespace chrono;
// using namespace atcoder;
// template <typename T>
// using ordered_set =
//    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long ll;
typedef long double ld;
const ll INF = 1e18;
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vll vector<ll>
#define rep(i, a, b) for(int i = a;i<b;i++)
#define ss second
#define ff first

template<typename T>
auto operator<<(ostream &os, T&v)->decltype(v.begin(), os){
	os << "[";
	int f = 0;
	for(auto i:v) {
		if(f++)os << ", ";
		os << i;
	}
	os << "]";
	return os;
}
template<typename F, typename S>
auto& operator<<(ostream &os, pair<F, S> const &p) {
	return os << "(" << p.first << ", " << p.second << ")";
}
void debug(){}
template<typename T, typename... V>
void debug(T t, V... v) {
	cerr << t;
	if(sizeof...(v)) {
		cerr << ", "; debug(v...);
	}
}
#ifdef LOCAL
#define dbg(x...) cerr << "[" << #x << "]: " << "["; debug(x); cerr << "]\n";
#define nl cerr << "\n";
#else
#define dbg(x...)
#define nl
#endif


vector<vector<long long> > g(80, vector<long long> (80, 0));
long long dp[80][80];
void solve() {
    int n;
    long long k;
    cin >> n >> k;
    long long sz1 = (n+1)>>1, sz2 = n - ((n+1)>>1);
    long long a[sz1], b[sz2];
    for(int i=0;i<n;i++) {
            if(i < sz1)cin >> a[i];
            else cin >> b[i-sz1];
    }
    vector<long long> suma;
    for(long long i = 0;i<(1ll<<sz1);i++) {
        long long s = 0;
        for(int j = 0;j<sz1;j++) {
            if(i&(1ll<<j))s += a[j];
        }
        suma.push_back(s);
    }
    long long ans = 0;
    sort(suma.begin(), suma.end());
    dbg(suma);
	for(long long i = 0;i<(1ll<<sz2);i++) {
        long long s = 0;
        for(int j = 0;j<sz1;j++) {
            if(i&(1ll<<j))s += b[j];
        }
        dbg(s, k-s);
        ans += (upper_bound(suma.begin(), suma.end(), k-s)) - suma.begin();
        
    }
    cout << ans << endl;
}
int main () {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t = 1;
	// cin >> t;
	while(t--) {
		solve();
	}
	return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1528 KB Output is correct
2 Correct 91 ms 2552 KB Output is correct
3 Correct 441 ms 8712 KB Output is correct
4 Correct 88 ms 2504 KB Output is correct
5 Correct 14 ms 1036 KB Output is correct
6 Correct 7 ms 716 KB Output is correct
7 Correct 13 ms 968 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 1476 KB Output is correct
2 Correct 29 ms 1532 KB Output is correct
3 Correct 178 ms 4652 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 7 ms 716 KB Output is correct
6 Correct 13 ms 968 KB Output is correct
7 Correct 13 ms 1044 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 2556 KB Output is correct
2 Correct 130 ms 4560 KB Output is correct
3 Correct 133 ms 4604 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 73 ms 4604 KB Output is correct
6 Correct 203 ms 8652 KB Output is correct
7 Correct 89 ms 4540 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 8776 KB Output is correct
2 Correct 26 ms 1476 KB Output is correct
3 Correct 10 ms 716 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 7 ms 776 KB Output is correct
6 Correct 180 ms 8720 KB Output is correct
7 Correct 13 ms 968 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 1476 KB Output is correct
2 Correct 84 ms 2564 KB Output is correct
3 Correct 8 ms 716 KB Output is correct
4 Correct 9 ms 784 KB Output is correct
5 Correct 86 ms 4612 KB Output is correct
6 Correct 21 ms 1500 KB Output is correct
7 Correct 219 ms 8712 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 354 ms 8800 KB Output is correct
2 Correct 29 ms 1520 KB Output is correct
3 Correct 9 ms 716 KB Output is correct
4 Correct 432 ms 8772 KB Output is correct
5 Correct 114 ms 4616 KB Output is correct
6 Correct 13 ms 1012 KB Output is correct
7 Correct 26 ms 1476 KB Output is correct