Robiłem pewne zadanie, w którym często korzystam z operacji bitowych i modulo, dla wygody zrobiłem 3 tablice long long
long long sum[MAXDP], cash[MAXN], ways[MAXDP];
jednak tak naprawdę takiego zakresu potrzebowała tylko tablica sum
. Zamieniłem kod na taki
int cash[MAXN], ways[MAXDP];
long long sum[MAXDP];
Mój program zdecydowanie przyśpieszył np w jedym teście z 0.39s do 0.24s. Czy operacje na long long są wolniejsze od tych na int?
Cały program:
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define ll long long
#define ull unsigned long long
const int MOD = 1e9 + 7, MAXN = 20, MAXDP = 1 << MAXN;
int cash[MAXN], ways[MAXDP];
ll sum[MAXDP];
bool seen[MAXDP];
void solve(){
int n;
cin >> n;
for (int i = 0; i < n; i++)
cin >> cash[i];
queue<int> que;
que.push(0);
ways[0] = 1;
seen[0] = true;
while (!que.empty()){
for (int i = 0; i < n; i++){
if ((que.front() & (1 << i)) == 0 && sum[que.front()] + cash[i] >= 0){
ways[que.front() | (1 << i)] = (ways[que.front()] + ways[que.front() | (1 << i)]) % MOD;
if (seen[que.front() | (1 << i)] == false){
seen[que.front() | (1 << i)] = true;
que.push(que.front() | (1 << i));
sum[que.front() | (1 << i)] = sum[que.front()] + cash[i];
}
}
}
que.pop();
}
cout << ways[(1 << n) - 1] % MOD << "\n";
}
void testcases(){
int t;
cin >> t;
while(t){
solve();
t--;
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(nullptr); cout.tie(nullptr);
//testcases();
solve();
return 0;
}
Gdyby ktoś chciał to tutaj link do zadania, niestety nie wiem czy jest możliwe obejrzenie go bez zalogowania się :/
https://szkopul.edu.pl/c/oki-dla-zaawansowanych/p/got/