← Real problems

dmopc21c9p1

easymathad-hocStatement on DMOJ

CP Lang

11 lineschecks
// dmopc21c9p1: neighbouring positive numbers sum to a[i]; count the first numbers that work.
// Each x is x1 or -x1 plus a constant, so positivity bounds x1 from below or above in turn.
let n = read<2..=1_000_000>()
var sign = 1
var c = 0
var ok = 1..=inf
for a in read<[n - 1]Int>():
    sign = -sign
    c = a - c
    ok = ok.clip(if sign < 0: ..c else: 1 - c..)
print(ok.len)

Accepted C++

58 lines · 1.68 s on the judge
#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
	cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
	cerr << t << " | ";
	dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
	cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
		 << ": ";                                          \
	dbgh(__VA_ARGS__)
#else
#define cerr   \
	if (false) \
	cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())

void solve() {
	int n;
	cin >> n;
	long arr[n - 1];
	for (auto& a : arr) {
		cin >> a;
	}
	long m = 1, b = 0;
	long mn = 1, mx = 1e18;
	for (auto& a : arr) {
		b = a - b;
		m *= -1;
		if (m == -1) {
			mx = min(mx, b - 1);
		} else {
			mn = max(mn, -b + 1);
		}
	}
	cout << max(long(0), mx - mn + 1) << endl;
}

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cin.exceptions(ios::failbit);
	solve();
}