Submission #3658052


Source Code Expand

Copy
#include <iostream>
#include <vector>
#include <utility>
#include <numeric>
#include <functional>
#include <stdio.h>
#include <math.h>
#include <string>
#include <algorithm>
#include <deque>
#include <queue>
#include <map>
#include <chrono>
using namespace std;
using ll = long long;


ll maxd(vector<ll> &v, ll maxa, ll k) {
	ll a = 1;
	while(maxa >= a) {
		a *= 2;
	}
	a /= 2;
	while (a > 0) {
		a /= 2;
		ll count = 0;
		for (auto i : v) {
			if ((i & a) >= a) {
				++count;
				if (count == k) {
					return a;
				}
			}
		}
	}
	return a;
}

void cut(vector<ll> &v, ll a) {
	auto itr = v.begin();
	while (itr != v.end())
	{
		if((*itr & a) < a)
		{
			itr = v.erase(itr);
		}
		else
		{
			itr++;
		}
	}
}

int main() {
	ll N, K;
	cin >> N >> K;
	ll s[1002][1002];
	for (ll i = 0; i != N; ++i) {
		for (ll j = 0; j <= N; ++j) {
			s[i][j] = 0;
		}
	}
	vector<ll> vs;
	for (ll i = 0; i != N; ++i) {
		ll a;
		cin >> a;
		for (ll j = 0; j <= i; ++j) {
			s[i + 1][j] = s[i][j] + a;
			vs.push_back(s[i + 1][j]);
		}
	}
	sort(begin(vs), end(vs), greater<ll>());
	ll out = 0;
	ll a = 1e14;
	while (a > 0) {
		a = maxd(vs, a, K);
		out += a;
		cut(vs, a);
		// for (auto i : vs) {
		// 	cout << i << endl;
		// }
		// cout << endl;
	}
	cout << out << endl;
}

Submission Info

Submission Time
Task B - Sum AND Subarrays
User taku0728
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1345 Byte
Status

Test Cases

Set Name Score / Max Score Test Cases
All 0 / 400 n-large-k-small1, n-large-k-small2, n-large-k-small3, n-large-k-small4, n-large-k-small5, n-medium-1, n-medium-2, n-medium-3, n-medium-4, n-medium-5, n-medium-6, n-medium-7, n-medium-k-small-1, n-medium-k-small-2, n-small-1, n-small-2, n-small-3, nk-large-1, nk-large-2, sample_01, sample_02
Case Name Status Exec Time Memory
n-large-k-small1
n-large-k-small2
n-large-k-small3
n-large-k-small4
n-large-k-small5
n-medium-1
n-medium-2
n-medium-3 8 ms 2944 KB
n-medium-4 102 ms 3580 KB
n-medium-5 20 ms 3072 KB
n-medium-6
n-medium-7
n-medium-k-small-1 14 ms 1152 KB
n-medium-k-small-2 1105 ms 6008 KB
n-small-1 2 ms 2432 KB
n-small-2 3 ms 2560 KB
n-small-3 2 ms 2304 KB
nk-large-1
nk-large-2
sample_01 1 ms 256 KB
sample_02 1 ms 256 KB