Submission #839670

#	Time	Username	Problem	Language	Result	Execution time	Memory
839670		Cookie	Holiday (IOI14_holiday)	C++14	0 / 100	5037 ms	54688 KiB

holiday

#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 = 3e5 + 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[mxn + 1], a[mxn + 1], dp2[mxn + 1];
int opt[mxn + 1], opt2[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]);
            }
        }
    }
    cout << 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());
}

Compilation message (stderr)

holiday.cpp: In function 'long long int solve()':
holiday.cpp:161:1: warning: no return statement in function returning non-void [-Wreturn-type]
  161 | }
      | ^

• Subtask 1: 0 / 7
• Subtask 2: 0 / 23
• Subtask 3: 0 / 17
• Subtask 4: 0 / 53