Codeforces#344 Div2 A問題

はじめに

Codeforces Round #344 Div. 2 Prob. A. Interview

問題:http://codeforces.com/contest/631/problem/A

ある配列xについて、lからrまでの区間ですべての要素のorをとったものを、f(x,l,r)と定義する。 与えられた2つの配列a,bについて、max f(a,l,r)+f(b,l,r)を求める。

考え方

lとrについて全探索するだけ。計算量はO(n^2)。Div2のAにしては難しい気がするし10分くらいかかった。

解法

#include <iostream>
#include <vector>

using namespace std;

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);

    long long ret=0;
    int n;
    cin >> n;
    vector<long long> a(n),b(n);
    for(int i = 0; i < n; ++i){
        cin >> a[i];
    }
    for(int i = 0; i < n; ++i){
        cin >> b[i];
    }

    for(int i = 0; i < n; ++i){
        long long ax = a[i];
        long long bx = b[i];
        ret = max(ret,ax+bx);
        for(int j = i+1; j < n; ++j){
            ax |= a[j];
            bx |= b[j];
            ret = max(ret,ax+bx);
        }
    }
    cout << ret << endl;

    return 0;
}