Submission #891644

#	Time	Username	Problem	Language	Result	Execution time	Memory
891644		vjudge1	모임들 (IOI18_meetings)	C++17	19 / 100	699 ms	1756 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;
using ll = long long;
using vll = vector<ll>;

vll solve(vector<int> V, int delta, int len) {
    stack<int> S;
    vll re;
    ll cur = 0;
    for(int i = 0; i < len; ++i) {
        while(!S.empty() && V[i + delta] > V[S.top() + delta]) {
            int p = S.top();
            S.pop();
            int p2 = 0;
            if(!S.empty()) p2 = S.top() + 1;
            cur -= 1ll * (p - p2 + 1) * V[p + delta];
        }
        int p = 0;
        if(!S.empty()) p = S.top() + 1;
        cur += 1ll * (i - p + 1) * V[i + delta];
        S.push(i);
        re.push_back(cur);
    }
    return re;
}

vll minimum_costs(vi H, vi L, vi R) {
    vector<int> S(H);
    vi RH = H;
    reverse(RH.begin(), RH.end());
    vi RS(RH);
    int n = H.size();
    vll RE;
    if(H.size() <= 5000 && L.size() <= 5000) {
        for(int q = 0; q < L.size(); ++q) {
            vll opt1 = solve(S, L[q], R[q] - L[q] + 1);
            vll opt2 = solve(RS, n - 1 - R[q], R[q] - L[q] + 1);
            reverse(opt2.begin(), opt2.end());
            ll re = opt1[0] + opt2[0];
            for(int i = 0; i < R[q] - L[q] + 1; i++)
                re = min(re, opt1[i] + opt2[i] - H[i + L[q]]);
            RE.push_back(re);
        }
        return RE;
    }
    return vll(L.size() + 1, -1);
}

Compilation message (stderr)

meetings.cpp: In function 'vll minimum_costs(vi, vi, vi)':
meetings.cpp:39:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         for(int q = 0; q < L.size(); ++q) {
      |                        ~~^~~~~~~~~~

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