oj.uz

답안 #825068

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
825068 2023-08-14T14:11:17 Z Wael 휴가 (IOI14_holiday) C++14
100 / 100
 2416 ms 22768 KB 
#include<bits/stdc++.h>
#include "holiday.h"
//#include "grader.cpp"
using namespace std;
#define F first
#define S second
typedef long long ll;
int const M = 1e5 + 10 , N = 30e5 + 10;
int s[M] , cnt[N] , Left[N] , Right[N] , cur = 1 , L , R , k , Index;
ll Size = (1 << 30) , ans , sum[N] , dp[M];
 
void Add(ll i , ll node = 1 , ll lx = 1 , ll rx = Size) { 
    if(i == 0) return;
    if(lx == rx) {
        sum[node] += lx;
        ++cnt[node];
        return;
    } 
    int mid = (lx + rx) / 2;
    if(i <= mid) {
        if(Left[node] == 0) Left[node] = ++cur;
        Add(i , Left[node] , lx , mid);
    } else {
        if(Right[node] == 0) Right[node] = ++cur;
        Add(i , Right[node] , mid + 1 , rx);
    }
    sum[node] = sum[Left[node]] + sum[Right[node]];
    cnt[node] = cnt[Left[node]] + cnt[Right[node]];
}
 
void Remove(ll i , ll node = 1 , ll lx = 1 , ll rx = Size) {
    if(i == 0) return;
    if(lx == rx) {
        sum[node] -= lx;
        --cnt[node];
        return;
    } 
    ll mid = (lx + rx) / 2;
    if(i <= mid) {
        if(Left[node] == 0) Left[node] = ++cur;
        Remove(i , Left[node] , lx , mid);
    } else {
        if(Right[node] == 0) Right[node] = ++cur;
        Remove(i , Right[node] , mid + 1 , rx);
    }
    sum[node] = sum[Left[node]] + sum[Right[node]];
    cnt[node] = cnt[Left[node]] + cnt[Right[node]];
}
 
ll Get(ll need , ll node = 1 , ll lx = 1 , ll rx = Size) { //cout << need << " " << lx << endl;
    if(node == 0) return 0;
    if(need <= 0) return 0;
    if(lx == rx) return min(need , (ll)cnt[node]) * lx;
    ll mid = (lx + rx) / 2;
    if(cnt[Right[node]] >= need) {
        //cout << lx << " " << rx << " " << cnt[Right[node]] << endl;
        return Get(need , Right[node] , mid + 1 , rx);
    }
    else {
        need -= cnt[Right[node]];
        return sum[Right[node]] + Get(need , Left[node] , lx , mid);
    }
}
 
void Move(int l , int r) {
    if(l > r) swap(l , r);
 
    while(L < l) {
        Remove(s[L]);
        ++L;
    }
 
    while(L > l) {
        --L;
        Add(s[L]);
    }
 
    while(R < r) {
        ++R;
        Add(s[R]);
    }
 
    while(R > r) {
        Remove(s[R]);
        --R;
    }
}
 
void Divide(int l , int r , int i , int j) { 
    //cout << "in = " <<  l << " " << r << " " << i << " " << j << endl;
    if(i > j) return;
    int mid = (i + j) / 2;
 
    ll mx = 0 , Optimal = mid;
    for(int I = l ; I <= r ; ++I) {
        Move(mid , I);
        //cout << sum[1] << endl;
        int d = k;
        d -= abs(mid - Index);
        d -= abs(mid - I);
        //cout << "d = " << d << endl;
        ll res = Get(d);
        if(res > mx) {
            mx = res;
            dp[mid] = res;
            Optimal = I;
        }
    }
 
    ans = max ( ans , mx );
 
    //cout << "mid = " << mid << " " << dp[mid] << endl;
    Divide(l , Optimal , i , mid - 1);
    Divide(Optimal , r , mid + 1 , j);
}
 
long long int findMaxAttraction(int n, int start, int D , int attraction[]) {
    ++start;
    k = D; Index = start;
    for(int i = 1 ; i <= n ; ++i) s[i] = attraction[i - 1];
 
    int d = D;
    for(int i = start ; i <= n ; ++i) {
        Add(s[i]);
        ans = max(ans , Get(d));
        --d;
    }
    for(int i = start ; i <= n ; ++i) Remove(s[i]);
 
    d = D;
    for(int i = start ; i >= 1 ; --i) {
        Add(s[i]);
        ans = max(ans , Get(d));
        --d;
    }
    for(int i = 1 ; i <= start ; ++i) Remove(s[i]);
 
    if(start > 1 && start < n) Divide(1 , start - 1 , start + 1 , n);
    if(start > 1 && start < n) Divide(start + 1 , n , 1 , start - 1 );
 
    return ans;
}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 0 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 1096 KB Output is correct
2 Correct 6 ms 1108 KB Output is correct
3 Correct 38 ms 1108 KB Output is correct
4 Correct 13 ms 1108 KB Output is correct
5 Correct 44 ms 980 KB Output is correct
6 Correct 13 ms 852 KB Output is correct
7 Correct 21 ms 948 KB Output is correct
8 Correct 26 ms 980 KB Output is correct
9 Correct 9 ms 724 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 1876 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 3 ms 1876 KB Output is correct
4 Correct 34 ms 1840 KB Output is correct
5 Correct 30 ms 1740 KB Output is correct
6 Correct 9 ms 1108 KB Output is correct
7 Correct 9 ms 768 KB Output is correct
8 Correct 8 ms 724 KB Output is correct
9 Correct 10 ms 724 KB Output is correct

Subtask #4
53.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 1108 KB Output is correct
2 Correct 64 ms 22768 KB Output is correct
3 Correct 977 ms 12032 KB Output is correct
4 Correct 40 ms 1624 KB Output is correct
5 Correct 8 ms 776 KB Output is correct
6 Correct 8 ms 724 KB Output is correct
7 Correct 8 ms 760 KB Output is correct
8 Correct 2382 ms 9544 KB Output is correct
9 Correct 2416 ms 9548 KB Output is correct