제출 #1190654

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1190654		alexdd	3단 점프 (JOI19_jumps)	C++20	19 / 100	4094 ms	5544 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
int n;
int a[500005];
int tole[500005],tori[500005],maxsuff[500005];
int solve(int le, int ri)
{
    maxsuff[ri+1] = 0;
    for(int i=ri;i>=le;i--)
    {
        maxsuff[i] = max(maxsuff[i+1], a[i]);
    }
    int rez=0;
    for(int c=le;c<=ri;c++)
    {
        int st = tole[c];
        if(st < le)
            continue;
        if(c + (c-st) <= ri)
            rez = max(rez, a[st] + a[c] + maxsuff[c + (c-st)]);
    }
    for(int st=le;st<=ri;st++)
    {
        int c = tori[st];
        if(c > ri)
            continue;
        if(c + (c-st) <= ri)
            rez = max(rez, a[st] + a[c] + maxsuff[c + (c-st)]);
    }
    return rez;
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=n;i++)
    {
        tole[i] = 0;
        for(int u=i-1;u>=1;u--)
        {
            if(a[u] >= a[i])
            {
                tole[i] = u;
                break;
            }
        }
        tori[i] = n+1;
        for(int u=i+1;u<=n;u++)
        {
            if(a[u] >= a[i])
            {
                tori[i] = u;
                break;
            }
        }
    }
    int q;
    cin>>q;
    while(q--)
    {
        int le,ri;
        cin>>le>>ri;
        cout<<solve(le,ri)<<"\n";
    }
    return 0;
}
/*

5
5 2 1 5 3
3
1 4
2 5
1 5



tori[i] = prima pozitie x din dreapta lui i cu a[x] >= a[i]
tole[i] = prima pozitie x din stanga lui i cu a[x] >= a[i]

daca ne fixam capatu stanga in le, centru o sa fie in intervalu le+1..tori[le]

daca ne fixam centru in c, capatu stanga o sa fie in tole[c]..c-1

*/

• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 0 / 27
• Subtask 4: 0 / 54