oj.uz

Submission #760183

# Submission time Handle Problem Language Result Execution time Memory
760183 2023-06-17T09:10:51 Z Unforgettablepl Beautiful row (IZhO12_beauty) C++17
100 / 100
 507 ms 205548 KB 
/*
ID: samikgo1
TASK:
LANG: C++
*/
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
typedef pair<ll,ll> pll;
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
#define f first
#define s second
//#define x first
//#define y second
const int INF = INT32_MAX;
const ll modulo = 1e4;
//#define int ll

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
//    freopen("input.in","r",stdin);
//    freopen("haybales.out","w",stdout);
    ll n;
    cin >> n;
    vector<pair<ll,ll>> arr(n);
    auto countbit = [](ll a){
        ll onesa = 0;
        ll backa = a;
        while(a){
            if(a%3==1)onesa++;
            a/=3;
        }
        return make_pair(bitset<32>(backa).count(),onesa);
    };
    for(pair<ll,ll>&a:arr){cin>>a.first;a=countbit(a.first);}
    vector<vector<ll>> DP(1<<n,vector<ll>(n));
    for (ll i = 0; i < n; i++)DP[1<<i][i]=1;
    for (ll subset = 2; subset < 1<<n; subset++) {
        for (ll end = 0; end < n; end++) {
            if(!(subset&(1<<end)))continue; //If end doesnt exist in subset there cant be a possible array ending with it
            ll previous = subset-(1<<end);
            for (ll i = 0; i < n; i++) {
                // Ending of previous array
                if(arr[end].first!=arr[i].first and arr[end].second!=arr[i].second)continue; // Not compatible
                DP[subset][end]+=DP[previous][i];
            }
        }
    }
    ll ans = 0;
    for(ll&i:DP[(1<<n)-1])ans+=i;
    cout << ans;
}

Compilation message

beauty.cpp: In function 'int32_t main()':
beauty.cpp:40:32: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long unsigned int'} and 'int' [-Wsign-compare]
   40 |     for (ll subset = 2; subset < 1<<n; subset++) {
      |                         ~~~~~~~^~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 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 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 320 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 5 ms 2644 KB Output is correct
12 Correct 5 ms 2644 KB Output is correct
13 Correct 22 ms 11092 KB Output is correct
14 Correct 98 ms 47444 KB Output is correct
15 Correct 128 ms 47420 KB Output is correct
16 Correct 105 ms 47456 KB Output is correct
17 Correct 108 ms 47436 KB Output is correct
18 Correct 107 ms 47512 KB Output is correct
19 Correct 491 ms 205472 KB Output is correct
20 Correct 507 ms 205548 KB Output is correct