oj.uz

Submission #925173

# Submission time Handle Problem Language Result Execution time Memory
925173 2024-02-10T23:06:31 Z heavylightdecomp Triple Jump (JOI19_jumps) C++17
27 / 100
 33 ms 18464 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define X first
#define Y second
using pii = pair<int,int>;
#define pb push_back
#define vt vector
#define f0r(i,a,b) for(auto i = (a); i != (b);i++)
#define r0f(i,a,b) for(auto i=(a);i>=(b);i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
// sim dor ris eni(x) rge rage dud debug 2eni 2dor
#define sim template<class c
#define dor > debug& operator<<
#define ris return *this
#define eni(x) sim> typename \
enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i)
sim> struct rge { c b,e; };
sim> rge<c> range(c i, c j) {
    return rge<c>{i,j};
}
sim> auto dud(c* x)->decltype(cout <<*x, 0);
sim> char dud(...);
#define cerr while(0) cerr
struct debug {
    ~debug() { cerr << endl; }
    eni(!=) { cerr << boolalpha << i; ris; }
    eni(==) { ris << range(all(i)); }
    sim, class b dor(pair<b,c> d) { 
        ris << "(" << d.X << ", " << d.Y << ")";
    }
    sim dor(rge<c> d) {
        *this << "{";
        f0r(i,d.b,d.e) *this << ", " + 2*(i==d.b) << *i;
        ris << "}";
    }
};
#define imie(r...) " [" << #r << ": " << (r) << "] "
//i only matches with nge(i)
//sweepline
//basic subtraction
signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int N; cin >> N; int idc;
    vt<int> ar(N), nge(N, -1), pge(N, -1);
    f0r(i,0,N) cin >> ar[i];
    cin >> idc >> idc >> idc;
    stack<int> non;
    //BUG: PUSH THE INDEX NOT THE VALUE
    f0r(i,0,N) {
        while(non.size() and ar[non.top()] <= ar[i]) {
            nge[non.top()] = i;
            non.pop();
        }
        non.push(i);
    }
    while(non.size()) non.pop();
    r0f(i,N-1,0) {
        while(non.size() and ar[non.top()] < ar[i]) {
            pge[non.top()] = i;
            non.pop();
        }
        non.push(i);
    }
    debug() << imie(pge) << imie(nge);
    vt<pii> imp; 
    f0r(i,0,N) {
        if(nge[i] != -1) imp.pb({i,nge[i]});
        if(pge[i] != -1) imp.pb({pge[i],i});
    }
    vt<int> suf(N,0);
    for(auto &[l,r] : imp) {
        //BUG: could be out of bounds
        if(r+r-l < N) suf[r+r-l] = max(suf[r+r-l], ar[l] + ar[r]);
    }
    int res = 0;
    f0r(i,1,N) {
        suf[i] = max(suf[i], suf[i-1]);
        res = max(res, suf[i] + ar[i]);
    }
    cout << res << '\n';

}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 604 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 31 ms 17024 KB Output is correct
2 Correct 26 ms 14732 KB Output is correct
3 Correct 23 ms 14108 KB Output is correct
4 Correct 33 ms 17896 KB Output is correct
5 Correct 32 ms 18464 KB Output is correct
6 Correct 26 ms 16996 KB Output is correct
7 Correct 30 ms 17204 KB Output is correct
8 Correct 32 ms 17604 KB Output is correct
9 Correct 27 ms 17684 KB Output is correct

Subtask #4
0 / 54.0

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