D. AND, OR and square sum

https://codeforces.com/contest/1368/problem/D

Problem - D - Codeforces

 

 

처음에 어떻게 풀 지 몰라서 힌트 받아서 풀었음ㅋㅋ x|y = x + y - (x&y) 공식을 사용하면 전체의 합이 일정하다는 걸 알 수 있다. 전체 합이 일정할 경우 숫자를 최대한 몰아줘야 제곱의 합이 최대가 된다.

 

풀이 방법은 먼저 각 자리수 별 비트 개수를 세고 → 비트 최대치를 사용해서 큰 수를 만든다음 → 제곱해서 답에 더해준다.

 

어제 비트마스크를 사용하는 문제를 풀어서 비트 연산이 어렵지 않았다ㅋㅋ 배운 걸 써먹으니 뿌듯하네

 

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <math.h>
#include <random>
#include <functional>
#include <assert.h>
#include <math.h>
#define all(x) (x).begin(), (x).end()
#define xx first
#define yy second
#define MOD ((i64)1e10)
 
using namespace std;
 
template<typename T, typename Pr = less<T>>
using pq = priority_queue<T, vector<T>, Pr>;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
 
int main()
{
    int n;
    scanf("%d", &n);
 
    vector<int> v(n);
    for (int i = 0; i < n; i++)
        scanf("%d", &v[i]);
 
    vector<int> count(22, 0);
    
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < 21; j++)
        {
            if (v[i] & (1<<j))
                count[j]++;
        }
    }
    
    i64 ans = 0;
    vector<int> zero(22, 0);
    while (count != zero)
    {
        i64 num = 0;
        for (int j = 0; j < 21; j++)
        {
            if (count[j] > 0)
            {
                count[j]--;
                num = num + (1 << j);
            }
        }
        ans += num * num;
    }
 
    printf("%lld", ans);
 
    return 0;
}