#include "meetings.h"
#include <cstdio>
#include <stdint.h>
#include <cstdlib>
#include <algorithm>
typedef long long ll;
static const ll INF=1e9+7;
std::vector<ll> minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R) {
int N=H.size();
H.insert(H.begin(),INF);
H.push_back(INF);
int Q=L.size();
for(int j=0;j<Q;j++){
L[j]++,R[j]++;
}
std::vector<ll> C(Q);
std::vector<int> ls(N+2),rs(N+2);
std::vector<ll> lcost(N+2),rcost(N+2);
std::vector<int> eps(N+2);
for(int i=0;i<eps.size();i++){
eps[i]=i;
}
std::random_shuffle(eps.begin(),eps.end());
for(int i=1;i<=N;i++){
ls[i]=i-1;
while(H[i]>H[ls[i]]||(H[i]==H[ls[i]]&&eps[i]>eps[ls[i]])){
lcost[i]=std::min(lcost[i]+ll(ls[i]-ls[ls[i]])*H[ls[i]],
lcost[ls[i]]+ll(i-ls[i])*H[ls[i]]);
ls[i]=ls[ls[i]];
}
//printf("ls[%d]=%d (%lld)\n",i,ls[i],lcost[i]);
}
for(int i=N;i>=1;i--){
rs[i]=i+1;
while(H[i]>H[rs[i]]||(H[i]==H[rs[i]]&&eps[i]>eps[rs[i]])){
rcost[i]=std::min(rcost[i]+ll(rs[rs[i]]-rs[i])*H[rs[i]],
rcost[rs[i]]+ll(rs[i]-i)*H[rs[i]]);
rs[i]=rs[rs[i]];
}
//printf("rs[%d]=%d (%lld)\n",i,rs[i],rcost[i]);
}
//printf("AAAAA\n");
for(int i=0;i<Q;i++){
std::vector<int> lseq,rseq;
for(int j=L[i];j<=R[i];j=rs[j]){
lseq.push_back(j);
//printf("Lseq: %d\n",j);
}
for(int j=R[i];j>=L[i];j=ls[j]){
rseq.push_back(j);
//printf("Rseq: %d\n",j);
}
int maxi=lseq.back();
ll best=(R[i]-L[i]+1LL)*H[maxi];
{
ll ac=(R[i]-maxi+1LL)*H[maxi];
for(int j=lseq.size()-2;j>=0;j--){
best=std::min(best,(lseq[j]-L[i]+1LL)*H[lseq[j]]+rcost[lseq[j]]+ac);
ac+=(lseq[j+1]-lseq[j])*1LL*H[lseq[j]];
}
}
{
ll ac=(maxi-L[i]+1LL)*H[maxi];
for(int j=rseq.size()-2;j>=0;j--){
best=std::min(best,(R[i]-rseq[j]+1LL)*H[rseq[j]]+lcost[rseq[j]]+ac);
ac+=(rseq[j]-rseq[j+1])*1LL*H[rseq[j]];
}
}
C[i]=best;
//printf("%lld\n",best);
}
return C;
}
Compilation message
meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:24:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<eps.size();i++){
~^~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
3 ms |
376 KB |
Output is correct |
3 |
Correct |
3 ms |
376 KB |
Output is correct |
4 |
Correct |
3 ms |
376 KB |
Output is correct |
5 |
Correct |
3 ms |
504 KB |
Output is correct |
6 |
Correct |
3 ms |
376 KB |
Output is correct |
7 |
Correct |
3 ms |
376 KB |
Output is correct |
8 |
Correct |
3 ms |
376 KB |
Output is correct |
9 |
Correct |
3 ms |
444 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
3 ms |
376 KB |
Output is correct |
3 |
Correct |
3 ms |
376 KB |
Output is correct |
4 |
Correct |
3 ms |
376 KB |
Output is correct |
5 |
Correct |
3 ms |
504 KB |
Output is correct |
6 |
Correct |
3 ms |
376 KB |
Output is correct |
7 |
Correct |
3 ms |
376 KB |
Output is correct |
8 |
Correct |
3 ms |
376 KB |
Output is correct |
9 |
Correct |
3 ms |
444 KB |
Output is correct |
10 |
Correct |
8 ms |
648 KB |
Output is correct |
11 |
Correct |
8 ms |
648 KB |
Output is correct |
12 |
Correct |
8 ms |
632 KB |
Output is correct |
13 |
Correct |
8 ms |
608 KB |
Output is correct |
14 |
Correct |
8 ms |
672 KB |
Output is correct |
15 |
Correct |
7 ms |
632 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
348 KB |
Output is correct |
2 |
Correct |
50 ms |
1804 KB |
Output is correct |
3 |
Correct |
151 ms |
6120 KB |
Output is correct |
4 |
Correct |
143 ms |
6208 KB |
Output is correct |
5 |
Correct |
77 ms |
6256 KB |
Output is correct |
6 |
Correct |
134 ms |
6136 KB |
Output is correct |
7 |
Correct |
157 ms |
6128 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
348 KB |
Output is correct |
2 |
Correct |
50 ms |
1804 KB |
Output is correct |
3 |
Correct |
151 ms |
6120 KB |
Output is correct |
4 |
Correct |
143 ms |
6208 KB |
Output is correct |
5 |
Correct |
77 ms |
6256 KB |
Output is correct |
6 |
Correct |
134 ms |
6136 KB |
Output is correct |
7 |
Correct |
157 ms |
6128 KB |
Output is correct |
8 |
Correct |
146 ms |
6132 KB |
Output is correct |
9 |
Correct |
133 ms |
6128 KB |
Output is correct |
10 |
Correct |
133 ms |
6184 KB |
Output is correct |
11 |
Correct |
150 ms |
6140 KB |
Output is correct |
12 |
Correct |
133 ms |
6136 KB |
Output is correct |
13 |
Correct |
135 ms |
6148 KB |
Output is correct |
14 |
Correct |
144 ms |
6144 KB |
Output is correct |
15 |
Correct |
148 ms |
6140 KB |
Output is correct |
16 |
Correct |
229 ms |
6128 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
3 ms |
376 KB |
Output is correct |
3 |
Correct |
3 ms |
376 KB |
Output is correct |
4 |
Correct |
3 ms |
376 KB |
Output is correct |
5 |
Correct |
3 ms |
504 KB |
Output is correct |
6 |
Correct |
3 ms |
376 KB |
Output is correct |
7 |
Correct |
3 ms |
376 KB |
Output is correct |
8 |
Correct |
3 ms |
376 KB |
Output is correct |
9 |
Correct |
3 ms |
444 KB |
Output is correct |
10 |
Correct |
8 ms |
648 KB |
Output is correct |
11 |
Correct |
8 ms |
648 KB |
Output is correct |
12 |
Correct |
8 ms |
632 KB |
Output is correct |
13 |
Correct |
8 ms |
608 KB |
Output is correct |
14 |
Correct |
8 ms |
672 KB |
Output is correct |
15 |
Correct |
7 ms |
632 KB |
Output is correct |
16 |
Correct |
2 ms |
348 KB |
Output is correct |
17 |
Correct |
50 ms |
1804 KB |
Output is correct |
18 |
Correct |
151 ms |
6120 KB |
Output is correct |
19 |
Correct |
143 ms |
6208 KB |
Output is correct |
20 |
Correct |
77 ms |
6256 KB |
Output is correct |
21 |
Correct |
134 ms |
6136 KB |
Output is correct |
22 |
Correct |
157 ms |
6128 KB |
Output is correct |
23 |
Correct |
146 ms |
6132 KB |
Output is correct |
24 |
Correct |
133 ms |
6128 KB |
Output is correct |
25 |
Correct |
133 ms |
6184 KB |
Output is correct |
26 |
Correct |
150 ms |
6140 KB |
Output is correct |
27 |
Correct |
133 ms |
6136 KB |
Output is correct |
28 |
Correct |
135 ms |
6148 KB |
Output is correct |
29 |
Correct |
144 ms |
6144 KB |
Output is correct |
30 |
Correct |
148 ms |
6140 KB |
Output is correct |
31 |
Correct |
229 ms |
6128 KB |
Output is correct |
32 |
Correct |
1798 ms |
44400 KB |
Output is correct |
33 |
Correct |
1087 ms |
44516 KB |
Output is correct |
34 |
Correct |
1464 ms |
44396 KB |
Output is correct |
35 |
Correct |
1743 ms |
44396 KB |
Output is correct |
36 |
Correct |
1053 ms |
44396 KB |
Output is correct |
37 |
Correct |
1429 ms |
44380 KB |
Output is correct |
38 |
Correct |
1788 ms |
44396 KB |
Output is correct |
39 |
Correct |
1736 ms |
44396 KB |
Output is correct |
40 |
Execution timed out |
5587 ms |
44796 KB |
Time limit exceeded |
41 |
Halted |
0 ms |
0 KB |
- |