Submission #102016


Source Code Expand

#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;

template <typename T>
class BinaryIndexedTree {

private:
	vector<T> data;

public:
	BinaryIndexedTree(int n) : data(n + 1) { }
	T sum(int i){
		T s = T();
		for(; i > 0; i -= i & -i){ s += data[i]; }
		return s;
	}
	void add(int i, const T &x){
		for(++i; i < static_cast<int>(data.size()); i += i & -i){
			data[i] += x;
		}
	}
};

int main(){
	ios_base::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	BinaryIndexedTree<ll> bit(n);
	for(int i = 0; i < n; ++i){
		int x;
		cin >> x;
		bit.add(i, x);
	}
	ll ans = bit.sum(n / 2);
	for(int i = 0, base = 0; i < m; ++i){
		int k;
		cin >> k;
		base = (base + k - 1) % n;
		if(base + n / 2 > n){
			ans = max(
				ans, bit.sum(base - n / 2) + bit.sum(n) - bit.sum(base));
		}else{
			ans = max(ans, bit.sum(base + n / 2) - bit.sum(base));
		}
	}
	cout << ans << endl;
	return 0;
}

Submission Info

Submission Time
Task J - Very Intellectual Card Game
User neteru_AA
Language C++ (G++ 4.6.4)
Score 100
Code Size 969 Byte
Status AC
Exec Time 70 ms
Memory 1584 KB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 18
Set Name Test Cases
All 1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 2, 3, 4, 5, 6, 7, 8, 9
Case Name Status Exec Time Memory
1 AC 22 ms 808 KB
10 AC 20 ms 804 KB
11 AC 21 ms 932 KB
12 AC 21 ms 804 KB
13 AC 51 ms 1440 KB
14 AC 41 ms 1064 KB
15 AC 70 ms 1572 KB
16 AC 70 ms 1560 KB
17 AC 68 ms 1584 KB
18 AC 68 ms 1572 KB
2 AC 21 ms 928 KB
3 AC 21 ms 804 KB
4 AC 21 ms 932 KB
5 AC 21 ms 928 KB
6 AC 21 ms 808 KB
7 AC 21 ms 808 KB
8 AC 21 ms 808 KB
9 AC 21 ms 740 KB