Submission #335928

#	Time	Username	Problem	Language	Result	Execution time	Memory
335928		Vladth11	Discharging (NOI20_discharging)	C++14	100 / 100	293 ms	89040 KiB

Discharging

#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debug_with_space(x) cerr << #x << " " << x << " "

using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <ll, pii> piii;

const ll NMAX = 1000001;
const ll INF = (1LL << 60);
const ll MOD = 1000000007;
const ll BLOCK = 101;
const ll nr_of_bits = 35;

struct functie{
    ll a, b;
    ll valoare(ll x){
        return a * x + b;
    }
};

functie tree[NMAX * 4];

void update(ll node, ll st, ll dr, functie x){
    if(st == dr){
        if(x.valoare(st) < tree[node].valoare(st)){
            swap(x, tree[node]);
        }
        return;
    }
    ll mid = (st + dr) / 2;
    ll xs = x.valoare(st);
    ll xm = x.valoare(mid);
    ll ts = tree[node].valoare(st);
    ll tm = tree[node].valoare(mid);
    if(xm < tm){
        if(xs < ts){
            swap(tree[node], x);
            update(node * 2 + 1, mid + 1, dr, x);
        }else{
            swap(tree[node], x);
            update(node * 2, st, mid, x);
        }
    }else{
        if(xs < ts){
            update(node * 2, st, mid, x);
        }else{
            update(node * 2 + 1, mid + 1, dr, x);
        }
    }
}

ll query(ll node, ll st, ll dr, ll col){
    if(st == dr){
        return tree[node].valoare(col);
    }
    ll mid = (st + dr) / 2;
    ll val = tree[node].valoare(col);
    if(col <= mid){
        return min(query(node * 2, st, mid, col), val);
    }else{
        return min(val, query(node * 2 + 1, mid + 1, dr, col));
    }
}

vector <pii> grupe;
ll dp[NMAX + 1];
ll v[NMAX];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    for(ll i = 0; i < 4 * NMAX; i++){
        tree[i].b = INF;
    }
    ll n, i, ind = 1;
    cin >> n;
    cin >> v[1];
    for(i = 2; i <= n; i++){
        cin >> v[i];
        if(v[i] > v[ind]){
            grupe.push_back({v[ind], ind});
            ind = i;
        }
    }
    grupe.push_back({v[ind], ind});
    dp[grupe.size() + 1] = 0;
    n++;
    for(i = grupe.size() ; i >= 1; i--){
        update(1, 1, n, {grupe[i - 1].first, dp[i + 1]});
        dp[i] = query(1, 1, n, (n - grupe[i - 1].second + 1 - 1));
    }
    cout << dp[1];
    return 0;
}

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