54 lines
899 B
C++
54 lines
899 B
C++
#include <bits/stdc++.h>
|
|
using namespace std;
|
|
|
|
typedef unsigned long long ull;
|
|
|
|
int main() {
|
|
ios::sync_with_stdio(0);
|
|
cin.tie(0);
|
|
|
|
char c;
|
|
deque<tuple<int, int, int>> blocks;
|
|
deque<tuple<int, int>> frees;
|
|
int i = 0, n = 0;
|
|
bool rfree = false;
|
|
while (cin >> c) {
|
|
c -= '0';
|
|
if (rfree) {
|
|
if (c > 0) {
|
|
frees.push_back({n, c});
|
|
}
|
|
} else {
|
|
blocks.push_back({i++, n, c});
|
|
}
|
|
rfree = !rfree;
|
|
n += c;
|
|
}
|
|
|
|
while (frees.size() > 0) {
|
|
auto &[bi, bx, bn] = blocks.back();
|
|
auto &[fx, fn] = frees[0];
|
|
if (fx > bx) {
|
|
break;
|
|
}
|
|
int nmoved = min(fn, bn);
|
|
bn -= nmoved;
|
|
fn -= nmoved;
|
|
blocks.push_front({bi, fx, nmoved});
|
|
if (fn == 0) {
|
|
frees.pop_front();
|
|
} else {
|
|
fx += nmoved;
|
|
}
|
|
if (bn == 0) {
|
|
blocks.pop_back();
|
|
}
|
|
}
|
|
|
|
ull sum = 0;
|
|
for (auto &[bi, bx, bn] : blocks) {
|
|
sum += (ull)bi * (bn * bx + bn * (bn - 1) / 2);
|
|
}
|
|
cout << sum << '\n';
|
|
}
|