제출 #1178056

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1178056		wowwowwow	Discharging (NOI20_discharging)	C++20	11 / 100	55 ms	4168 KiB

Discharging

#include <bits/stdc++.h>
#define ll long long
#define all(v) v.begin(),v.end()
#define MASK(i) (1LL << (i))
#define ii pair<int,int>
#define fi first
#define se second
#define endl '\n'
#define forr(i,l,r,add) for(int i = l;i <= r; i = i + add)
#define fodd(i,l,r,sub) for(int i = l;i >= r ; i = i - sub)
template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {if (a > b) {a = b; return true;} return false;}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {if (a < b) {a = b; return true;} return false;}

using namespace std;

mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
#define rand rd

long long Rand(long long l , long long h){
	assert(l <= h);
	return l + 1ll * rd() % (h - l + 1) * (rd() % (h - l + 1)) % (h - l + 1);
}


//////////////////////////////////////////////////////////// end of template ////////////////////////////////////////////////////////////

const int MAX = 1e6 + 5;
int a[MAX];
int n;
vector <int> save;
int val[MAX];
int num;
ll dp[MAX];

struct line{
    int a , b;
    ll c;
    int l , r;
};

line convex[MAX];
int SZ = 0;

ll calc(int val , line &x){
    return x.c + x.a * 1ll * (x.b - val + 1);
}

void INP(){
    cin >> n;
    forr(i , 1 , n , 1) cin >> a[i];
    save.push_back(1);
    forr(i , 2 , n , 1){
        if(a[save[save.size() - 1]] < a[i]) save.push_back(i);
    }
    for(auto x : save) val[++num] = x;
    convex[++SZ] = {a[val[num]] , n , 0 , 1 , MAX};
    val[num + 1] = n;
    fodd(i , num , 1 , 1){
        int l = 1 , r = SZ , mid , ans = 0;
        while(l <= r){
            mid = l + r >> 1;
            if(convex[mid].r >= val[i + 1]) ans = mid , r = mid - 1;
            else l = mid + 1;
        }
        dp[i] = calc(val[i + 1] , convex[ans]);
        line tmp = {a[val[i]] , n , dp[i] , 0 , 0};
        while(SZ > 0){
            l = 1 , r = val[i + 1] - 1 , ans = 0;
            while(l <= r){
                mid = l + r >> 1;
                if(calc(mid , convex[SZ]) >= calc(mid , tmp)) ans = mid , l = mid + 1;
                else r = mid - 1;
            }
            if(ans >= convex[SZ].r) SZ--;
            else if(ans == 0) break;
            else {
                convex[SZ].l = ans + 1;
                convex[++SZ] = tmp;
                convex[SZ].l = 1 , convex[SZ].r = ans;
                break;
            }
        }
        if(SZ == 0) convex[++SZ] = tmp , convex[SZ].l = 1 , convex[SZ].r = n;
    }
    //forr(i , 1 , SZ , 1) cout << convex[i].a << ' ' << convex[i].b << ' ' << convex[i].c << ' ' << convex[i].l << ' ' << convex[i].r << endl;
    forr(i , 1 , SZ , 1){
        if(convex[i].l <= 1){
            cout << calc(1 , convex[i]);
            return;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    #define TASK "DISCHARGING"
    //freopen(TASK".inp" , "r" , stdin);
    //freopen(TASK".out" , "w" , stdout);
    INP();
    return 0;
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 13
• Subtask 3: 0 / 25
• Subtask 4: 11 / 11
• Subtask 5: 0 / 14
• Subtask 6: 0 / 28