Submission #2780745


Source Code Expand

Copy
#include <bits/stdc++.h>
#define REP(i, a, n) for(ll i = ((ll) a); i < ((ll) n); i++)
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;

int main(void) {
  ll N;
  cin >> N;
  vector<ll> A(1LL << N);
  REP(i, 0, 1LL << N) cin >> A[i];

  const ll INF = 1LL << 50;
  vector<pll> dp(1LL << N);
  REP(i, 0, 1LL << N) dp[i] = pll(i, 0);
  REP(i, 0, 1LL << N) {
    REP(j, 0, N) if(!(i & (1LL << j))) {
      pll x = dp[i | (1LL << j)], y = dp[i];
      vector<ll> s = { x.first, x.second, y.first, y.second };
      sort(s.begin(), s.end());
      s.erase(unique(s.begin(), s.end()), s.end());
      sort(s.begin(), s.end(), [&](ll p, ll q) { return A[p] > A[q]; });
      dp[i | (1LL << j)] = pll(s[0], s[1]);
    }
  }

  ll ans = 0;
  REP(i, 1, 1LL << N) {
    ans = max(ans, A[dp[i].first] + A[dp[i].second]);
    cout << ans << endl;
  }
}

Submission Info

Submission Time
Task E - Or Plus Max
User kshinya
Language C++14 (GCC 5.4.1)
Score 700
Code Size 890 Byte
Status
Exec Time 695 ms
Memory 9216 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt, sample_03.txt
All 700 / 700 sample_01.txt, sample_02.txt, sample_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt
Case Name Status Exec Time Memory
sample_01.txt 1 ms 256 KB
sample_02.txt 1 ms 256 KB
sample_03.txt 1 ms 256 KB
subtask_1_01.txt 1 ms 256 KB
subtask_1_02.txt 1 ms 256 KB
subtask_1_03.txt 76 ms 1152 KB
subtask_1_04.txt 4 ms 256 KB
subtask_1_05.txt 1 ms 256 KB
subtask_1_06.txt 21 ms 512 KB
subtask_1_07.txt 21 ms 512 KB
subtask_1_08.txt 1 ms 256 KB
subtask_1_09.txt 1 ms 256 KB
subtask_1_10.txt 38 ms 768 KB
subtask_1_11.txt 1 ms 256 KB
subtask_1_12.txt 82 ms 1408 KB
subtask_1_13.txt 2 ms 256 KB
subtask_1_14.txt 694 ms 9216 KB
subtask_1_15.txt 1 ms 256 KB
subtask_1_16.txt 695 ms 9216 KB
subtask_1_17.txt 631 ms 7680 KB
subtask_1_18.txt 678 ms 9088 KB
subtask_1_19.txt 679 ms 9216 KB
subtask_1_20.txt 657 ms 9216 KB
subtask_1_21.txt 695 ms 9216 KB
subtask_1_22.txt 691 ms 9216 KB
subtask_1_23.txt 688 ms 9216 KB
subtask_1_24.txt 627 ms 7680 KB
subtask_1_25.txt 680 ms 9088 KB
subtask_1_26.txt 674 ms 9216 KB
subtask_1_27.txt 649 ms 9216 KB
subtask_1_28.txt 687 ms 9216 KB
subtask_1_29.txt 689 ms 9216 KB