| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 839672 |
2023-08-30T11:53:51 Z |
Cookie |
Holiday (IOI14_holiday) |
C++14 |
|
1573 ms |
13996 KB |
#include"holiday.h"
#include<bits/stdc++.h>
#include<fstream>
using namespace std;
//ifstream fin("FEEDING.INP");
//ofstream fout("FEEDING.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const ll mod = 1e9 + 7;
const int mxn = 1e5 + 5, mxr = 25e3, sq = 500, mxv = 200, mxvv = 130, pr = 31;
const ll inf = 1e9;
int n, s, d;
vt<int>comp;
int find(int x){
return(lower_bound(comp.begin(), comp.end(), x) - comp.begin() + 1);
}
struct ST{
ll st[4 * mxn + 1];
void init(){
memset(st, 0, sizeof(st));
}
void upd(int nd, int l, int r, int id, ll v){
if(id < l || id > r)return;
if(l == r){
assert(l == id);
st[nd] += v;
return;
}
int mid = (l + r) >> 1;
upd(nd << 1, l, mid, id, v); upd(nd << 1 | 1, mid + 1, r, id, v);
st[nd] = st[nd << 1] + st[nd << 1 | 1];
}
ll get(int nd, int l, int r, int ql, int qr){
if(ql > r || qr < l)return(0);
if(ql <= l && qr >= r){
//cout << nd << " " << st[nd] << " ";
return(st[nd]);
}
int mid = (l + r) >> 1;
return(get(nd << 1, l, mid, ql, qr) + get(nd << 1 | 1, mid + 1, r, ql, qr));
}
int kth(int nd, int l, int r, int k){
if(l == r)return(l);
int mid = (l + r) >> 1;
if(st[nd << 1 | 1] >= k){
return(kth(nd << 1 | 1, mid + 1, r, k));
}else{
return(kth(nd << 1, l, mid, k - st[nd << 1 | 1]));
}
}
};
ST sm, cnt;
void add(int x){
sm.upd(1, 0, n, find(x), x); cnt.upd(1, 0, n, find(x), 1);
assert(find(x) != 0);
}
void rem(int x){
sm.upd(1, 0, n, find(x), -x); cnt.upd(1, 0, n, find(x), -1);
}
ll ans = 0, dp[3 * mxn + 1], a[mxn + 1], dp2[3 * mxn + 1];
int opt[3 * mxn + 1], opt2[3 * mxn + 1];
ll get(int s){
int last = cnt.kth(1, 0, n, s), tot = cnt.get(1, 0, n, last + 1, n);
ll res = sm.get(1, 0, n, last + 1, n);
//cout << s << " " << last << " " << tot << "\n";
if(last != 0){
res += 1LL * (s - tot) * comp[last - 1];
}
return(res);
}
void solvef(int l, int r, int bestl, int bestr){
if(l > r)return;
int mid = (l + r) >> 1;
ll res = -1, bestid = -1;
for(int i = bestl; i <= min(bestr, s + mid); i++){
add(a[i]);
//cout << i << " ";
ll cand = get(mid - (i - s));
if(cand > res){
res = cand; bestid = i;
}
}
dp[mid] = res; opt[mid] = bestid;
//cout << mid << " " << bestid << " " << res << "\n";
ans = max(ans, dp[mid]);
for(int i = min(bestr, s + mid); i >= bestid; i--){
rem(a[i]);
}
solvef(mid + 1, r, bestid, bestr);
for(int i = bestid - 1; i >= bestl; i--){
rem(a[i]);
}
solvef(l, mid - 1, bestl, bestid);
}
void solveg(int l, int r, int bestl, int bestr){
if(l > r)return;
int mid = (l + r) >> 1;
ll res = -1, bestid = -1;
for(int i = bestr; i >= max(bestl, s - 1 - mid); i--){
add(a[i]);
//cout << i << " ";
ll cand = get(mid - (s - 1 - i));
if(cand > res){
res = cand; bestid = i;
}
}
dp2[mid] = res; opt2[mid] = bestid;
//cout << mid << " " << bestid << " " << res << "\n";
ans = max(ans, dp2[mid]);
for(int i = max(bestl, s - 1 - mid); i <= bestid; i++){
rem(a[i]);
}
solveg(mid + 1, r, bestl, bestid);
for(int i = bestid + 1; i <= bestr; i++){
rem(a[i]);
}
solveg(l, mid - 1, bestid, bestr);
}
ll solve(){
for(int i = 1; i <= n; i++)comp.pb(a[i]);
s++;
sort(comp.begin(), comp.end());
solvef(1, d, s, n);
sm.init(); cnt.init();
if(s != 1){
solveg(0, d - 1, 1, s - 1);
for(int i = 0; i <= d; i++){
ll lft = d - i - (opt[i] - (s - 1));
if(lft >= 0){
ans = max(ans, dp[i] + dp2[lft]);
}
}
for(int i = 0; i < d; i++){
ll lft = d - (i + 1) - (s - opt2[i]);
if(lft >= 0){
ans = max(ans, dp[lft] + dp2[i]);
}
}
}
return(ans);
}
long long int findMaxAttraction(int N, int S, int D, int attraction[]) {
n = N; s = S; d = D;
for(int i = 0; i < n; i++){
a[i + 1] = attraction[i];
}
return(solve());
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
6868 KB |
Output is correct |
| 2 |
Correct |
3 ms |
6868 KB |
Output is correct |
| 3 |
Correct |
3 ms |
6996 KB |
Output is correct |
| 4 |
Correct |
3 ms |
6968 KB |
Output is correct |
| 5 |
Correct |
3 ms |
6868 KB |
Output is correct |
| 6 |
Correct |
3 ms |
6972 KB |
Output is correct |
| 7 |
Correct |
3 ms |
6868 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
829 ms |
10484 KB |
Output is correct |
| 2 |
Correct |
842 ms |
10872 KB |
Output is correct |
| 3 |
Correct |
825 ms |
10720 KB |
Output is correct |
| 4 |
Correct |
863 ms |
10804 KB |
Output is correct |
| 5 |
Correct |
986 ms |
9872 KB |
Output is correct |
| 6 |
Correct |
373 ms |
9600 KB |
Output is correct |
| 7 |
Correct |
493 ms |
8892 KB |
Output is correct |
| 8 |
Correct |
614 ms |
8956 KB |
Output is correct |
| 9 |
Correct |
261 ms |
10108 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
7168 KB |
Output is correct |
| 2 |
Correct |
19 ms |
7236 KB |
Output is correct |
| 3 |
Correct |
25 ms |
7216 KB |
Output is correct |
| 4 |
Correct |
29 ms |
7092 KB |
Output is correct |
| 5 |
Correct |
23 ms |
7120 KB |
Output is correct |
| 6 |
Correct |
8 ms |
6996 KB |
Output is correct |
| 7 |
Correct |
6 ms |
6968 KB |
Output is correct |
| 8 |
Correct |
7 ms |
6968 KB |
Output is correct |
| 9 |
Correct |
6 ms |
6968 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
989 ms |
13996 KB |
Output is correct |
| 2 |
Correct |
1201 ms |
11952 KB |
Output is correct |
| 3 |
Correct |
254 ms |
8292 KB |
Output is correct |
| 4 |
Correct |
18 ms |
6996 KB |
Output is correct |
| 5 |
Correct |
7 ms |
6996 KB |
Output is correct |
| 6 |
Correct |
7 ms |
6996 KB |
Output is correct |
| 7 |
Correct |
6 ms |
6996 KB |
Output is correct |
| 8 |
Correct |
1563 ms |
10260 KB |
Output is correct |
| 9 |
Correct |
1573 ms |
10244 KB |
Output is correct |
