Submission #8940640
Source Code Expand
#include <bits/stdc++.h> #define ll long long #define ff first #define ss second #define pb push_back using namespace std; const int N = 1e6+69, mod = 1e9+9; ll n,m,x,y,a,b,c,d,t,k,ans=1e18,cur,l,r; ll A[N],dp[N],mx[N],mx1[N]; int main() { cin>>n; for(int i=0;i<(1<<n);i++) cin>>A[i]; if(A[0]<A[1]){ mx[1] = 1; mx1[1] = 0; } else { mx[1] = 0; mx1[1] = 1; } dp[1] = A[0]+A[1]; mx[0] = 0; for(int i=2;i<(1<<n);i++){ mx[i] = i; for(int j=0;j<n;j++) if( (i>>j) & 1){ //cout<< (i^(1<<j)) <<endl; if(A[mx[i]] <= A[ mx[i^(1<<j)] ] && mx[i] != mx[i^(1<<j)] ){ mx1[i] = mx[i]; mx[i] = mx[i^(1<<j)]; } else if(A[mx1[i]] < A[ mx[i^(1<<j)] ] && mx1[i] != mx[i^(1<<j)] && mx[i] != mx[i^(1<<j)]) { mx1[i] = mx[i^(1<<j)]; } } dp[i] = max(A[mx[i]] + A[mx1[i]],dp[i-1]); //cout<<mx[i]<<" "<<mx1[i]<<" "<<i<<endl; } for(int i=1;i<(1<<n);i++) cout<<dp[i]<<" "; }
Submission Info
Submission Time | |
---|---|
Task | E - Or Plus Max |
User | giorgikob |
Language | C++14 (GCC 5.4.1) |
Score | 700 |
Code Size | 1259 Byte |
Status | AC |
Exec Time | 161 ms |
Memory | 19456 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 700 / 700 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt, sample_03.txt |
All | 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 | AC | 2 ms | 6400 KB |
sample_02.txt | AC | 2 ms | 6400 KB |
sample_03.txt | AC | 2 ms | 6400 KB |
subtask_1_01.txt | AC | 2 ms | 6400 KB |
subtask_1_02.txt | AC | 2 ms | 6400 KB |
subtask_1_03.txt | AC | 15 ms | 6784 KB |
subtask_1_04.txt | AC | 3 ms | 6400 KB |
subtask_1_05.txt | AC | 2 ms | 6400 KB |
subtask_1_06.txt | AC | 7 ms | 6528 KB |
subtask_1_07.txt | AC | 7 ms | 6528 KB |
subtask_1_08.txt | AC | 2 ms | 6400 KB |
subtask_1_09.txt | AC | 2 ms | 6400 KB |
subtask_1_10.txt | AC | 9 ms | 6656 KB |
subtask_1_11.txt | AC | 2 ms | 6400 KB |
subtask_1_12.txt | AC | 20 ms | 7040 KB |
subtask_1_13.txt | AC | 3 ms | 6400 KB |
subtask_1_14.txt | AC | 161 ms | 19456 KB |
subtask_1_15.txt | AC | 2 ms | 6400 KB |
subtask_1_16.txt | AC | 161 ms | 19456 KB |
subtask_1_17.txt | AC | 109 ms | 17920 KB |
subtask_1_18.txt | AC | 150 ms | 19328 KB |
subtask_1_19.txt | AC | 151 ms | 19456 KB |
subtask_1_20.txt | AC | 151 ms | 19456 KB |
subtask_1_21.txt | AC | 161 ms | 19456 KB |
subtask_1_22.txt | AC | 161 ms | 19456 KB |
subtask_1_23.txt | AC | 160 ms | 19456 KB |
subtask_1_24.txt | AC | 110 ms | 17920 KB |
subtask_1_25.txt | AC | 149 ms | 19328 KB |
subtask_1_26.txt | AC | 152 ms | 19456 KB |
subtask_1_27.txt | AC | 150 ms | 19456 KB |
subtask_1_28.txt | AC | 161 ms | 19456 KB |
subtask_1_29.txt | AC | 161 ms | 19456 KB |