# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
835125 | 2023-08-23T08:47:54 Z | tolbi | Meetings (IOI18_meetings) | C++17 | 5500 ms | 5656 KB |
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define tol(bi) (1LL<<((ll)(bi))) #include "meetings.h" vector<long long> minimum_costs(vector<int> arr, vector<int> L, vector<int> R) { ll q = L.size(); ll n = arr.size(); vector<ll> ansarr(q,0); for (ll qu = 0; qu < q; ++qu) { ll l = L[qu]; ll r = R[qu]; vector<ll> leftdp(r-l+1); vector<ll> rightdp(r-l+1); vector<ll> stak; for (ll i = l; i <= r; i++){ while (stak.size() && arr[stak.back()]<=arr[i]){ stak.pop_back(); }; if (stak.size()==0){ leftdp[i-l]=(i-l+1)*arr[i]; } else { leftdp[i-l]=leftdp[stak.back()-l]+arr[i]*(i-stak.back()); } stak.push_back(i); } stak.clear(); for (ll i = r; i >= l; i--){ while (stak.size() && arr[stak.back()]<=arr[i]){ stak.pop_back(); } if (stak.size()==0){ rightdp[i-l]=(r-i+1)*arr[i]; } else { rightdp[i-l]=rightdp[stak.back()-l]+arr[i]*(stak.back()-i); } stak.push_back(i); } ll ans = LONG_LONG_MAX; for (ll i = l; i <= r; i++){ ans=min(ans,leftdp[i-l]+rightdp[i-l]-arr[i]); } ansarr[qu]=ans; } return ansarr; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 340 KB | Output is correct |
3 | Correct | 1 ms | 340 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
5 | Correct | 1 ms | 340 KB | Output is correct |
6 | Correct | 1 ms | 316 KB | Output is correct |
7 | Correct | 1 ms | 336 KB | Output is correct |
8 | Correct | 1 ms | 340 KB | Output is correct |
9 | Correct | 1 ms | 340 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 340 KB | Output is correct |
3 | Correct | 1 ms | 340 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
5 | Correct | 1 ms | 340 KB | Output is correct |
6 | Correct | 1 ms | 316 KB | Output is correct |
7 | Correct | 1 ms | 336 KB | Output is correct |
8 | Correct | 1 ms | 340 KB | Output is correct |
9 | Correct | 1 ms | 340 KB | Output is correct |
10 | Correct | 127 ms | 676 KB | Output is correct |
11 | Correct | 475 ms | 672 KB | Output is correct |
12 | Correct | 128 ms | 768 KB | Output is correct |
13 | Correct | 469 ms | 660 KB | Output is correct |
14 | Correct | 56 ms | 680 KB | Output is correct |
15 | Correct | 63 ms | 668 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 1710 ms | 1704 KB | Output is correct |
3 | Execution timed out | 5580 ms | 5656 KB | Time limit exceeded |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 1710 ms | 1704 KB | Output is correct |
3 | Execution timed out | 5580 ms | 5656 KB | Time limit exceeded |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 340 KB | Output is correct |
3 | Correct | 1 ms | 340 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
5 | Correct | 1 ms | 340 KB | Output is correct |
6 | Correct | 1 ms | 316 KB | Output is correct |
7 | Correct | 1 ms | 336 KB | Output is correct |
8 | Correct | 1 ms | 340 KB | Output is correct |
9 | Correct | 1 ms | 340 KB | Output is correct |
10 | Correct | 127 ms | 676 KB | Output is correct |
11 | Correct | 475 ms | 672 KB | Output is correct |
12 | Correct | 128 ms | 768 KB | Output is correct |
13 | Correct | 469 ms | 660 KB | Output is correct |
14 | Correct | 56 ms | 680 KB | Output is correct |
15 | Correct | 63 ms | 668 KB | Output is correct |
16 | Correct | 0 ms | 212 KB | Output is correct |
17 | Correct | 1710 ms | 1704 KB | Output is correct |
18 | Execution timed out | 5580 ms | 5656 KB | Time limit exceeded |
19 | Halted | 0 ms | 0 KB | - |