#include <bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i, n) for(int i = 1; i <= n; i++)
#define FOR(i, a, b) for(auto i = a; i <= b; i++)
#define FORD(i, a, b) for(auto i = a; i >= b; i--)
template<class T> bool maximize(T& a, T b) { if(a < b) return a = b, 1; return 0; }
template<class T> bool minimize(T& a, T b) { if(a > b) return a = b, 1; return 0; }
mt19937 rng(time(0));
const int N = (int)2e5 + 7;
int a[N];
int n;
namespace Subtask1
{
const int maxN = 2007;
int f[maxN][maxN];
bool Check()
{
return n <= 2000;
}
void Calc(int k)
{
REP(i, n)
{
if(f[i - 1][k]) f[i][k] = f[i - 1][k];
if(i - 2 > 0 and f[i - 2][k - 1]) maximize(f[i][k], f[i - 2][k - 1] + a[i]);
}
}
void Solve()
{
REP(i, n)
f[i][1] = max(a[i], f[i - 1][1]);
REP(i, (n + 1) / 2)
{
if(i > 1) Calc(i);
int ans = 0;
REP(j, n)
maximize(ans, f[j][i]);
cout << ans << '\n';
}
}
}
namespace Subtask2
{
bool del[N];
int ans[(N + 1) / 2];
int nxt[N], prv[N];
void Solve()
{
priority_queue<pair<int, int>> pq;
REP(i, n)
{
pq.push({a[i], i});
nxt[i] = i + 1;
prv[i] = i - 1;
}
nxt[0] = 1;
prv[n + 1] = n;
int cnt = 0, s = 0;
while(pq.size() and cnt < (n + 1) / 2)
{
pair<int, int> x = pq.top();
pq.pop();
int id = x.second;
int w = x.first;
if(del[id])
continue;
s += w;
++cnt;
maximize(ans[cnt], s);
del[nxt[id]] = 1;
del[prv[id]] = 1;
a[id] = a[nxt[id]] + a[prv[id]] - w;
nxt[id] = nxt[nxt[id]];
prv[id] = prv[prv[id]];
prv[nxt[id]] = nxt[prv[id]] = id;
pq.push({a[id], id});
}
REP(i, (n + 1) / 2)
cout << ans[i] << '\n';
}
}
signed main(void)
{
cin.tie(nullptr)->sync_with_stdio(false);
#define TASK ""
if(fopen(TASK".INP", "r"))
{
freopen(TASK".INP", "r", stdin);
freopen(TASK".OUT", "w", stdout);
}
cin >> n;
REP(i, n)
cin >> a[i];
// if(Subtask1::Check()) return Subtask1::Solve(), 0;
return Subtask2::Solve(), 0;
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
candies.cpp: In function 'int main()':
candies.cpp:99:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
99 | freopen(TASK".INP", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
candies.cpp:100:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
100 | freopen(TASK".OUT", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |