oj.uz

Submission #797420

# Submission time Handle Problem Language Result Execution time Memory
797420 2023-07-29T10:55:30 Z fatemetmhr Triple Jump (JOI19_jumps) C++17
19 / 100
 307 ms 87104 KB 
// Be name khoda // 
 
#include <bits/stdc++.h>
 
#define all(x) x.begin(), x.end()
#define pb     push_back
#define fi     first
#define se     second
#define mp     make_pair
 
typedef long long ll;
 
using namespace std;
 
const int maxn5 = 5e3 + 10;
const int maxn  = 1e6 + 10;
const int lg    = 20;
const ll inf    = 1e18;
 
int a[maxn5], rmq[maxn5][maxn5];
ll mx[maxn5], out[maxn];
vector <pair<pair<int, int>, int>> req;
 
int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
 
	int n; cin >> n;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        rmq[i][i] = a[i];
    }
    for(int i = 0; i < n; i++) for(int j = i + 1; j < n; j++)
        rmq[i][j] = max(rmq[i][j - 1], a[j]);
    int q; cin >> q;
    for(int i = 0; i < q; i++){
        int l, r; cin >> l >> r;
        l--; r--;
        req.pb({{r, l}, i});
    }
    sort(all(req));
    int ind = 0;
    for(int i = 0; i < n; i++){
        for(int j = i - 2; j >= 0; j--)
            mx[j] = max({mx[j + 1], mx[j], ll(a[j]) + a[i] + rmq[j + 1][(i + j) / 2]});
        while(ind < req.size() && req[ind].fi.fi == i){
            out[req[ind].se] = mx[req[ind].fi.se];
            ind++;
        }
    }
    for(int i = 0; i < q; i++)
        cout << out[i] << '\n';
}

Compilation message

jumps.cpp: In function 'int main()':
jumps.cpp:45:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         while(ind < req.size() && req[ind].fi.fi == i){
      |               ~~~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 704 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 716 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 704 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 716 KB Output is correct
11 Correct 267 ms 86992 KB Output is correct
12 Correct 285 ms 86900 KB Output is correct
13 Correct 267 ms 86900 KB Output is correct
14 Correct 267 ms 86932 KB Output is correct
15 Correct 270 ms 87104 KB Output is correct
16 Correct 271 ms 86320 KB Output is correct
17 Correct 272 ms 86448 KB Output is correct
18 Correct 293 ms 86324 KB Output is correct
19 Correct 307 ms 86904 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 56 ms 41760 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 704 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 716 KB Output is correct
11 Correct 267 ms 86992 KB Output is correct
12 Correct 285 ms 86900 KB Output is correct
13 Correct 267 ms 86900 KB Output is correct
14 Correct 267 ms 86932 KB Output is correct
15 Correct 270 ms 87104 KB Output is correct
16 Correct 271 ms 86320 KB Output is correct
17 Correct 272 ms 86448 KB Output is correct
18 Correct 293 ms 86324 KB Output is correct
19 Correct 307 ms 86904 KB Output is correct
20 Runtime error 56 ms 41760 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -