#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll INF = 1e18;
int Q,N;
vector<int> H;
vector<vector<int>> indices(20+1);
unordered_map<ll,int> dp;
ll f (int i, int j, ll hMax) {
if (i > j) return 0;
if (hMax == 1) return j-i+1;
ll h = (ll)i + (ll)(1e5)*j + (ll)(1e10)*hMax;
if (dp.count(h) > 0) {
// cout << "test";
return dp[h];
}
auto left = lower_bound(indices[hMax].begin(),indices[hMax].end(),i);
auto right = upper_bound(indices[hMax].begin(),indices[hMax].end(),j);
if (left == right) return f(i,j,hMax-1);
ll res = INF;
for (auto it = left; it != right; it++) {
int x = (it == left ? i : *prev(it)+1);
int y = *it-1;
ll val = f(x,y,hMax-1) + (ll)hMax*(j-i+1 - (y-x+1));
res = min(res,val);
}
int x = *prev(right)+1; int y = j;
ll val = f(x,y,hMax-1) + (ll)hMax*(j - i + 1 - (y-x+1));
res = min(res,val);
dp[h] = res;
return res;
}
vector<long long> minimum_costs(vector<int> tempH, vector<int> L, vector<int> R) {
H = tempH; Q = L.size(); N = H.size();
for (int i = 0; i < N; i++) indices[H[i]].push_back(i);
vector<long long> C(Q,-1);
dp.reserve(22*N);
for (int q = 0; q < Q; q++) {
C[q] = f(L[q],R[q],20);
}
return C;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
2 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
2 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
695 ms |
4644 KB |
Output is correct |
3 |
Execution timed out |
5525 ms |
23604 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
695 ms |
4644 KB |
Output is correct |
3 |
Execution timed out |
5525 ms |
23604 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
2 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |