| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 231506 | toloraia | Holiday (IOI14_holiday) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define F first
#define S second
#define mp make_pair
#define pb push_back
//#define ll __int128
#define ll long long
#define int long long
//#define int __int128
#define LEFT(a) ((a)<<1)
#define RIGHT(a) (LEFT(a) + 1)
#define MID(a,b) ((a+b)>>1)
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define y1 y122
/*
#pragma GCC optimize ("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2,fma")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC target ("avx2")
#pragma GCC optimization ("unroll-loops")
#pragma comment(linker, "/STACK: 20000000005")
*/
using namespace std;
const int N = 1000005, MOD = 998244353;
int M, val[N];
struct node {
node *l, *r;
int cnt, sum;
node() {
l = r = NULL;
cnt = sum = 0;
}
};
node *u;
int X;
void turn (node *&t, int l, int r){
if (X < l || r < X)
return;
if (t == NULL)
t = new node();
else {
u = t;
t = new node();
*t = *u;
}
if (l == r){
t->cnt = 1;
t->sum = val[X];
return;
}
int mid = l + r >> 1;
if (X <= mid)
turn (t->l, l, mid);
else
turn (t->r, mid + 1, r);
t->cnt = t->sum = 0;
if (t->l){
t->cnt += t->l->cnt;
t->sum += t->l->sum;
}
if (t->r){
t->cnt += t->r->cnt;
t->sum += t->r->sum;
}
}
int datvla (node *&t, int l, int r){
if (X < 0)
return 0;
if (t == NULL)
return 0;
if (t->cnt <= X)
return t->sum;
int num = 0, S = 0;
if (t->l){
num = t->l->cnt;
S = t->l->sum;
}
int mid = l + r >> 1;
if (X <= num)
return datvla (t->l, l, mid);
X -= num;
return S + datvla (t->r, mid+1, r);
}
int D;
node *root[N];
vector < int > DP;
int T;
int F (int x){
if (T == 0)
return x-1;
else
return x*2;
}
void go (int l, int r, int L, int R){
int mid = l + r >> 1;
int fr = L, pas = 0;
for (int i = L; i <= R; i++){
X = mid - F(i);
pas = datvla (root[i], 0, M);
if (pas > DP[mid]){
DP[mid] = pas;
fr = i;
}
}
if (l < mid)
go (l, mid-1, L, fr);
if (mid < r)
go (mid+1, r, fr, R);
}
vector < int > solve (vector < int > V){
int n = V.size();
DP = vector < int > (D+1, 0);
if (n == 0)
return DP;
root[0] = new node();
for (int i = 1; i <= n; i++){
root[i] = root[i-1];
X = V[i-1];
turn (root[i], 0, M);
}
go (1, D, 1, n);
return DP;
}
main()
{
ios_base::sync_with_stdio(0);
int n, start;
cin >> n >> start >> D;
M = n;
vector < pair < int, int > > B (n);
vector < int > A(n);
for (int i = 0; i < n; i++){
cin >> B[i].F;
B[i].S = i;
}
sort (B.begin(), B.end());
reverse (B.begin(), B.end());
for (int i = 0; i < n; i++){
int ind = B[i].S;
A[ind] = i;
val[i] = B[i].F;
}
int ans = 0;
vector < int > v, DP1, DP2;
v.clear();
for (int i = start; i < n; i++){
v.pb (A[i]);
}
T = 0;
DP1 = solve (v);
v.clear();
//v.pb (M);
for (int i = start-1; i >= 0; i--){
//v.pb (M);
v.pb (A[i]);
}
T = 1;
DP2 = solve (v);
for (int i = 0; i <= D; i++)
ans = max (ans, DP1[i] + DP2[D - i]);
v.clear();
for (int i = start; i >= 0; i--){
v.pb (A[i]);
}
T = 0;
DP1 = solve (v);
v.clear();
//v.pb (M);
for (int i = start+1; i < n; i++){
//v.pb (M);
v.pb (A[i]);
}
T = 1;
DP2 = solve (v);
for (int i = 0; i <= D; i++)
ans = max (ans, DP1[i] + DP2[D - i]);
cout << ans << endl;
}