oj.uz

Submission #891643

# Submission time Handle Problem Language Result Execution time Memory
891643 2023-12-23T12:31:03 Z vjudge1 Meetings (IOI18_meetings) C++17
0 / 100
 13 ms 2444 KB 
#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 -= (p - p2 + 1) * V[p + delta];
        }
        int p = 0;
        if(!S.empty()) p = S.top() + 1;
        cur += (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(auto it : opt1)
           //     cout << it << " ";
           // cout << "\n";
           // for(auto it : opt2)
           //     cout << it << " ";
           // cout << "\n";
           // cout << "\n";
            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

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
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 1 ms 604 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 1 ms 604 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 13 ms 2444 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 13 ms 2444 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 1 ms 604 KB Output isn't correct
3 Halted 0 ms 0 KB -