oj.uz

Submission #851911

# Submission time Handle Problem Language Result Execution time Memory
851911 2023-09-20T19:13:46 Z kderylo Ice Hockey World Championship (CEOI15_bobek) C++17
60 / 100
 1000 ms 115400 KB 
#include <iostream>
#include <set>
#include <map>
using namespace std;
long long tab[50];
set<long long>war;
map<long long,long long>mapka;
void calculate_values(int ile)
{
    for(int i=0;i<(1<<ile);i++){
        long long suma=0;
        for(int j=0;j<ile;j++){
            if((i&(1<<j))>0){
                suma+=tab[j];
            }
        }
        war.insert(suma);
        mapka[suma]++;
    }
}
long long calculate_result(int start,int rozmiar,long long limit)
{
    long long wyn=0;
    for(int i=0;i<(1<<rozmiar);i++){
        long long suma=0;
        for(int j=0;j<rozmiar;j++){
            if((i&(1<<j))>0){
                suma+=tab[start+j];
            }
        }
        long long pom=limit-suma;
        auto it=war.upper_bound(pom);
        if(it!=war.begin()){
            it--;
            wyn+=mapka[*it];
        }
    }
    return wyn;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int ile;
    long long limit;
    cin>>ile>>limit;
    for(int i=0;i<ile;i++){
        cin>>tab[i];
    }
    if(ile==1){
        if(tab[0]<=limit){
            cout<<"2";
        }
        else{
            cout<<"1";
        }
        return 0;
    }
    calculate_values(ile/2);
    auto it=war.begin();
    long long l=0;
    while(it!=war.end()){
        l+=mapka[*it];
        mapka[*it]=l;
        it++;
    }
    cout<<calculate_result(ile/2,ile-(ile/2),limit);

    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 1624 KB Output is correct
2 Correct 388 ms 19040 KB Output is correct
3 Execution timed out 1040 ms 50788 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 2384 KB Output is correct
2 Correct 69 ms 5960 KB Output is correct
3 Correct 206 ms 1500 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 6 ms 344 KB Output is correct
6 Correct 29 ms 3420 KB Output is correct
7 Correct 43 ms 7432 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 12156 KB Output is correct
2 Correct 380 ms 14280 KB Output is correct
3 Correct 405 ms 14236 KB Output is correct
4 Correct 1 ms 548 KB Output is correct
5 Correct 66 ms 432 KB Output is correct
6 Correct 336 ms 2560 KB Output is correct
7 Correct 309 ms 29008 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1014 ms 57728 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 7504 KB Output is correct
2 Correct 391 ms 29164 KB Output is correct
3 Correct 23 ms 3928 KB Output is correct
4 Correct 24 ms 3928 KB Output is correct
5 Correct 80 ms 444 KB Output is correct
6 Correct 51 ms 7512 KB Output is correct
7 Execution timed out 1063 ms 115400 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1062 ms 115096 KB Time limit exceeded
2 Halted 0 ms 0 KB -