Submission #116263

#	Time	Username	Problem	Language	Result	Execution time	Memory
116263		RezwanArefin01	Meetings (IOI18_meetings)	C++17	19 / 100	5598 ms	5080 KiB

meetings

#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;

typedef long long ll; 

const int N = 1e6; 
int n, q, a[N]; 

ll solve(int l, int r) {
    vector<ll> dp(n + 1, 0); 
    vector<int> q(r - l + 3, -1); 

    int idx = 0; 
    ll sum = 0; 

    q[++idx] = l - 1; 
    for(int i = l; i <= r; ++i) {
        while(idx > 1 && a[i] >= a[q[idx]]) {
            sum -= (ll) (q[idx] - q[idx - 1]) * a[q[idx]];
            --idx; 
        }
        q[++idx] = i; 
        sum += (ll) (q[idx] - q[idx - 1]) * a[q[idx]]; 
        dp[i] = sum;
    }

    idx = sum = 0; 
    q[++idx] = r + 1; 
    for(int i = r; i >= l; --i) {
        while(idx > 1 && a[i] >= a[q[idx]]) {
            sum -= (ll) (q[idx - 1] - q[idx]) * a[q[idx]];
            --idx; 
        }
        q[++idx] = i; 
        sum += (ll) (q[idx - 1] - q[idx]) * a[q[idx]]; 
        dp[i] += sum;
    }

    ll ans = 1e18;
    for(int i = l; i <= r; ++i) {
        ans = min(ans, dp[i] - a[i]);
    }
    return ans; 
}

vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
    n = H.size(), q = L.size();
    copy(H.begin(), H.end(), a + 1); 

    vector<ll> ret(q);
    for(int i = 0; i < q; ++i) {
        ret[i] = solve(++L[i], ++R[i]);
    }

    return ret; 
}

• Subtask 1: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40