Submission #3656058
Source Code Expand
/** * File : B.cpp * Author : Kazune Takahashi * Created : 11/24/2018, 8:10:20 PM * Powered by Visual Studio Code */ #include <iostream> #include <iomanip> // << fixed << setprecision(xxx) #include <algorithm> // do { } while ( next_permutation(A, A+xxx) ) ; #include <vector> #include <string> // to_string(nnn) // substr(m, n) // stoi(nnn) #include <complex> #include <tuple> #include <queue> #include <stack> #include <map> // if (M.find(key) != M.end()) { } #include <set> #include <functional> #include <random> // auto rd = bind(uniform_int_distribution<int>(0, 9), mt19937(19920725)); #include <chrono> // std::chrono::system_clock::time_point start_time, end_time; // start = std::chrono::system_clock::now(); // double elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(end_time-start_time).count(); #include <cctype> #include <cassert> #include <cmath> #include <cstdio> #include <cstdlib> #include <list> using namespace std; #define DEBUG 0 // change 0 -> 1 if we need debug. typedef long long ll; // const int dx[4] = {1, 0, -1, 0}; // const int dy[4] = {0, 1, 0, -1}; // const int C = 1e6+10; // const ll M = 1000000007; int N, K; ll a[1010]; ll sum[1010]; list<ll> V; int main() { cin >> N >> K; for (auto i = 0; i < N; i++) { cin >> a[i]; } sum[0] = 0; for (auto i = 0; i < N; i++) { sum[i + 1] = sum[i] + a[i]; } for (auto i = 0; i <= N; i++) { for (auto j = 0; j < i; j++) { V.push_back(sum[i] - sum[j]); } } /* for (auto x : V) { cerr << x << endl; } */ for (int i = 45; i >= 0; i--) { int cnt = 0; int L = V.size(); for (auto it = V.begin(); it != V.end(); it++) { if (((*it) >> i) & 1) { cnt++; } } if (cnt >= K) { // cerr << "i = " << i << ", cnt = " << cnt << endl; auto it = V.begin(); while (it != V.end()) { ll t = *it; if ((t >> i) & 1) { it++; } else { it = V.erase(it); } } } } auto it = V.begin(); ll ans = *it; for (auto i = 0; i < K; i++) { ans = ans & (*it); it++; } cout << ans << endl; }
Submission Info
Submission Time | |
---|---|
Task | B - Sum AND Subarrays |
User | kazunetakahashi |
Language | C++14 (GCC 5.4.1) |
Score | 400 |
Code Size | 2313 Byte |
Status | AC |
Exec Time | 54 ms |
Memory | 16000 KB |
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 400 / 400 | ||
Status |
|
Set Name | Test Cases |
---|---|
All | 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 | AC | 48 ms | 15872 KB |
n-large-k-small2 | AC | 48 ms | 15872 KB |
n-large-k-small3 | AC | 48 ms | 15872 KB |
n-large-k-small4 | AC | 45 ms | 15872 KB |
n-large-k-small5 | AC | 46 ms | 15872 KB |
n-medium-1 | AC | 22 ms | 7936 KB |
n-medium-2 | AC | 35 ms | 12672 KB |
n-medium-3 | AC | 2 ms | 512 KB |
n-medium-4 | AC | 5 ms | 1408 KB |
n-medium-5 | AC | 3 ms | 768 KB |
n-medium-6 | AC | 40 ms | 14208 KB |
n-medium-7 | AC | 23 ms | 8320 KB |
n-medium-k-small-1 | AC | 2 ms | 512 KB |
n-medium-k-small-2 | AC | 10 ms | 3456 KB |
n-small-1 | AC | 1 ms | 256 KB |
n-small-2 | AC | 2 ms | 384 KB |
n-small-3 | AC | 1 ms | 256 KB |
nk-large-1 | AC | 54 ms | 16000 KB |
nk-large-2 | AC | 48 ms | 15872 KB |
sample_01 | AC | 1 ms | 256 KB |
sample_02 | AC | 1 ms | 256 KB |