oj.uz

Submission #585958

# Submission time Handle Problem Language Result Execution time Memory
585958 2022-06-29T15:39:11 Z jasmin Meetings (IOI18_meetings) C++14
19 / 100
 5500 ms 2440 KB 
#include<bits/stdc++.h>
using namespace std;
#include<meetings.h>
#define int long long

const int inf=1e18;
int maxh=20;

int cost(int l, int r, vector<int32_t>& h){
    if(r<l) return 0;
    if(l==r) return h[l];

    int mmax=0; int ind=l;
    for(int i=l; i<=r; i++){
        if(h[i]>mmax){
            mmax=h[i];
            ind=i;
        }
    }

    int left=cost(l, ind-1, h)+(r-ind+1)*mmax;
    int right=cost(ind+1, r, h)+(ind-l+1)*mmax;
    return min(left, right);
}

vector<int> minimum_costs(vector<int32_t> h, vector<int32_t> l, vector<int32_t> r){
   int n=h.size(); 
   int q=r.size();

   vector<int> ans(q, inf);
    for(int i=0; i<q; i++){
        ans[i]=cost(l[i], r[i], h);
    }
   return ans;
}

/*signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, q;
    cin >> n>> q;
    vector<int32_t> h(n);
    for(int i=0; i<n; i++){
        cin >> h[i];
    }
    vector<int32_t> l(q);
    vector<int32_t> r(q);
    for(int i=0; i<q; i++){
        cin >> l[i] >> r[i];
    }

    vector<int> ans=minimum_costs(h, l, r);
    for(auto e: ans){
        cout << e << "\n";
    }
}*/

Compilation message

meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:27:8: warning: unused variable 'n' [-Wunused-variable]
   27 |    int n=h.size();
      |        ^

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 312 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 304 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 8 ms 340 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 312 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 304 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 8 ms 340 KB Output is correct
10 Correct 246 ms 556 KB Output is correct
11 Correct 684 ms 552 KB Output is correct
12 Correct 216 ms 536 KB Output is correct
13 Correct 708 ms 540 KB Output is correct
14 Correct 3807 ms 692 KB Output is correct
15 Correct 125 ms 544 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 276 KB Output is correct
2 Execution timed out 5505 ms 2440 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 276 KB Output is correct
2 Execution timed out 5505 ms 2440 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 312 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 304 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 8 ms 340 KB Output is correct
10 Correct 246 ms 556 KB Output is correct
11 Correct 684 ms 552 KB Output is correct
12 Correct 216 ms 536 KB Output is correct
13 Correct 708 ms 540 KB Output is correct
14 Correct 3807 ms 692 KB Output is correct
15 Correct 125 ms 544 KB Output is correct
16 Correct 1 ms 276 KB Output is correct
17 Execution timed out 5505 ms 2440 KB Time limit exceeded
18 Halted 0 ms 0 KB -