Cod sursa(job #2785728)

Utilizator ElizaTElla Rose ElizaT Data 19 octombrie 2021 12:22:09
Problema Xerox Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <bits/stdc++.h>

using namespace std;

const int N = 22;
int dp[(1 << N) + 5];

int main()
{
    ifstream fin("coins.in");
    ofstream fout("coins.out");
    long long n,prev,x,cnt = 0,s,ans = 0;
    fin >> n;
    for (int i = 1;i <= N;i++)
        dp[(1 << i) - 1] = 1;
    for (int i = 0;i < (1 << N) - 1;i++) {
        prev = N;
        for (int j = N - 1;j >= 0;j--) {
            x = (i & (1 << j));
            if (x && prev != N)
                dp[i - (1 << j) + (1 << prev)] = max(1 - dp[i], dp[i - (1 << j) + (1 << prev)]);
            else if (!x)
                prev = j;
        }
    }
    for (int i = 0;i < n;i++) {
        s = 0;
        cnt = 0;
        for (int j = 0;j < N;j++) {
            fin >> x;
            if (x == 1) {
                s += (1 << j);
                cnt++;
            }
        }
        ans += 1ll * cnt * dp[s];
    }
    fout << ans;
    return 0;
}