oj.uz

Submission #616022

# Submission time Handle Problem Language Result Execution time Memory
616022 2022-07-31T18:09:14 Z Ahmadsm2005 Triple Jump (JOI19_jumps) C++17
27 / 100
 50 ms 19928 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
int N,Q,A[500000],L,R,C[500000];
vector<array<int,3>>PA;
int CALC(){
    stack<pair<int,int>>F;
    for(int i = 0; i < N; i += 1){
        while(F.size()){
            pair<int,int>TOP = F.top();
            PA.push_back({TOP.second, i, i * 2 - TOP.second});
            if(TOP.first > A[i])break;
            F.pop();
        }
        F.push({A[i],i});
    }
    int MX = 0;
    for(int i = 0; i < PA.size();i += 1){
        MX = max(MX,C[PA[i][2]] + A[PA[i][0]] + A[PA[i][1]]);
    }
    return MX;
}
void CALC2(){
    for(int i = 0; i < 500000; i += 1)C[i] = (int)-3e8;
    for(int i = N - 1; i >= 0; i -= 1){
        C[i] = max(C[i + 1], A[i]);
    }
}
int32_t main()
{
    cin.tie(0),iostream::sync_with_stdio(0);
    cin>>N;
    for(int i = 0; i < N; i += 1){
        cin>>A[i];
    }
    CALC2();
    cout<<CALC();
    cin>>Q;
    vector<array<int,3>>STO;
    for(int i = 0; i < Q; i += 1){
        cin>>L>>R;
        STO.push_back({L,R,i});
    }
    sort(STO.rbegin(),STO.rend());
}

Compilation message

jumps.cpp: In function 'long long int CALC()':
jumps.cpp:18:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for(int i = 0; i < PA.size();i += 1){
      |                    ~~^~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4164 KB Output is correct
2 Incorrect 3 ms 4168 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4164 KB Output is correct
2 Incorrect 3 ms 4168 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 19928 KB Output is correct
2 Correct 30 ms 13732 KB Output is correct
3 Correct 35 ms 15752 KB Output is correct
4 Correct 50 ms 19904 KB Output is correct
5 Correct 50 ms 19920 KB Output is correct
6 Correct 37 ms 19260 KB Output is correct
7 Correct 37 ms 19136 KB Output is correct
8 Correct 39 ms 19140 KB Output is correct
9 Correct 41 ms 19572 KB Output is correct

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4164 KB Output is correct
2 Incorrect 3 ms 4168 KB Output isn't correct
3 Halted 0 ms 0 KB -