#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>
#include <chrono>
#include <random>
#include <functional>
using namespace std;
#define int long long
const int N = 2001;
const int INF = 1e18 + 129;
int n;
int a[N];
int mapl[N];
int mapr[N];
int summ(int l, int r) {
int ans = 0;
for (int i = 0; i < r - l + 1; i++) {
if (i & 1) {
ans -= a[l + i];
} else {
// cerr << "add " << a[l + i] << endl;
ans += a[l + i];
}
}
return ans;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
set<pair<int, int>> seg;
for (int i = 1; i <= n; i++) {
mapl[i] = i;
mapr[i] = i;
seg.insert({i, i});
}
auto ers = [&](int l, int r) {
// cerr << "hr " << l << ' ' << r << endl;
auto it = seg.lower_bound({l, r});
auto prv = it;
if (it != seg.begin()) prv--;
auto nxt = it;
if (it != seg.end()) nxt++;
if (l == 1 && r == n) {
seg.erase({l, r});
return;
}
if (l == 1) {
pair<int, int> we = *it;
pair<int, int> next = *(nxt);
seg.erase(we);
seg.erase(next);
seg.insert({l, next.second});
return;
}
if (r == n) {
pair<int, int> we = *it;
pair<int, int> prev = *(prv);
seg.erase(we);
seg.erase(prev);
seg.insert({prev.first, r});
return;
}
// cerr << "full erase " << l << ' ' << r << endl;
// cerr << "was " << seg.size() << endl;
pair<int, int> we = *it;
pair<int, int> next = *(nxt);
pair<int, int> prev = *(prv);
// cerr << we.first << ' ' << we.second << endl;
// cerr << prev.first << ' ' << prev.second << endl;
// cerr << next.first << ' ' << next.second << endl;
seg.erase(prev);
seg.erase(we);
seg.erase(next);
seg.insert({prev.first, next.second});
// cerr << "now " << seg.size() << endl;
};
int curr = 0;
vector<int> ans;
while (!seg.empty()) {
int mx = -INF;
int lm = -1;
int rm = -1;
for (auto [l, r] : seg) {
if (summ(l, r) > mx) {
mx = summ(l, r);
lm = l;
rm = r;
}
}
// cerr << "before " << seg.size() << ' ' << mx << endl;
ers(lm, rm);
curr += mx;
ans.push_back(curr);
}
for (auto t : ans) {
cout << t << ' ';
}
cout << endl;
// cerr << summ(4, 4) << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
