oj.uz

Submission #314984

# Submission time Handle Problem Language Result Execution time Memory
314984 2020-10-21T19:46:10 Z mohamedsobhi777 Ice Hockey World Championship (CEOI15_bobek) C++14
100 / 100
 370 ms 33264 KB 
#include <bits/stdc++.h>

#pragma GCC optimize("-Ofast")
//#pragma GCC optimize("trapv")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")

#define I inline void
#define S struct
#define vi vector<int>
#define vii vector<pair<int, int>>
#define pii pair<int, int>
#define pll pair<ll, ll>

using namespace std;
using ll = long long;
using ld = long double;

const int N = 2e5 + 7, mod = 1e9 + 7;
const ll inf = 2e18;

// How interesting!

ll n, m;

void make(vector<ll> &v)
{
        vector<ll> ret;
        int sz = (int)v.size();
        for (int i = 0; i < (1 << sz); ++i)
        {
                ll sum = 0;
                for (int j = 0; j < sz; ++j)
                {
                        if (i & (1 << j))
                        {
                                sum += v[j];
                        }
                }
                ret.push_back(sum);
        }
        sort(ret.begin(), ret.end());
        v = ret;
}

int main()
{
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        //freopen("in.in", "r", stdin);
        cin >> n >> m;
        vector<ll> lhs, rhs;
        for (int i = 0; i < n; ++i)
        {
                ll x;
                cin >> x;
                if (i < n / 2)
                        lhs.push_back(x);
                else
                        rhs.push_back(x);
        }
        make(lhs);
        make(rhs);
        ll ans = 0;
        int j = (int)rhs.size() - 1;
        for (int i = 0; i < (int)lhs.size(); ++i)
        {
                while (j >= 0 && lhs[i] + rhs[j] > m)
                        --j;
                ans += j + 1;
        }
        cout << ans;
        return 0;
}

/*
        - bounds sir (segtree = 4N, eulerTour = 2N, ...)
        - a variable defined twice?
        - will overflow?
        - is it a good complexity?
        - don't mess up indices (0-indexed vs 1-indexed)
        - reset everything between testcases. 
*/

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 3052 KB Output is correct
2 Correct 84 ms 8544 KB Output is correct
3 Correct 370 ms 33216 KB Output is correct
4 Correct 86 ms 8544 KB Output is correct
5 Correct 15 ms 2424 KB Output is correct
6 Correct 9 ms 1404 KB Output is correct
7 Correct 20 ms 2424 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 4456 KB Output is correct
2 Correct 31 ms 3056 KB Output is correct
3 Correct 150 ms 16724 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 7 ms 1348 KB Output is correct
6 Correct 19 ms 2424 KB Output is correct
7 Correct 20 ms 2416 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 5652 KB Output is correct
2 Correct 131 ms 10844 KB Output is correct
3 Correct 130 ms 10712 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 91 ms 10836 KB Output is correct
6 Correct 309 ms 33216 KB Output is correct
7 Correct 127 ms 10712 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 20928 KB Output is correct
2 Correct 30 ms 3056 KB Output is correct
3 Correct 10 ms 1404 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 9 ms 1404 KB Output is correct
6 Correct 264 ms 20940 KB Output is correct
7 Correct 19 ms 2424 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 3052 KB Output is correct
2 Correct 83 ms 8540 KB Output is correct
3 Correct 10 ms 1404 KB Output is correct
4 Correct 11 ms 1404 KB Output is correct
5 Correct 93 ms 10712 KB Output is correct
6 Correct 29 ms 3056 KB Output is correct
7 Correct 349 ms 33216 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 361 ms 33220 KB Output is correct
2 Correct 31 ms 3056 KB Output is correct
3 Correct 10 ms 1404 KB Output is correct
4 Correct 366 ms 33264 KB Output is correct
5 Correct 120 ms 16720 KB Output is correct
6 Correct 19 ms 2412 KB Output is correct
7 Correct 40 ms 4456 KB Output is correct