Submission #1126357

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126357		heavylightdecomp	Mountains (IOI17_mountains)	C++20	100 / 100	30 ms	31992 KiB

mountains

#include<bits/stdc++.h>
using namespace std;
#define int int64_t
#define i32 signed
#define X first
#define Y second
#define pb push_back
using pii = pair<int,int>;
#define vt vector
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#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 debug(x) {auto _x=x;cerr<<#x<<": "<<_x<<'\n';};
//walk with fixed l and moving r
//the adjacent deev is the starting point

vt<vt<int>> dp;
int n;
i32 maximum_deevs(vt<i32> h) { //BUG: 1-indexing
    n = sz(h);
    vt<int> y (n+5);
    f0r(i,1,n+1) y[i] = h[i-1];
    dp = vt<vt<int>> (n+5, vt<int> (n+5));
    f0r(i,1,n+1) dp[i][i] = dp[i][i+1] = 1;
    r0f(l,n,1) {
        int uuu = l+1;
        //[uuu+1, r-1]
        for(int r = l+2; r <= n; r++) {
            int ha = y[r]-y[l], hb = y[uuu]-y[l];
            int hc = r-l, hd = uuu-l;
            //ha/hc >= hb / hd  to be seen 
            if(ha*hd >= hb*hc) { //i can be seen!!!!!
                // debug("wow"); debug(l); debug(r);
                dp[l][r] = max(dp[l+1][r], dp[l][uuu-1] + dp[uuu+1][r-1]);
                uuu = r;
            } else { //i can't be seen so it really don't matter????
                // debug("can't see anything") debug(l) debug(r)
                // debug(l); debug(r); debug(uuu);
                dp[l][r] = max(dp[l+1][r], dp[l][uuu-1] + dp[uuu+1][r]);
            }
        }
    }

    // f0r(i,1,n+1) {
    //     f0r(j,i,n+1) {
    //         cerr << dp[i][j] << ' ';
    //     }
    //     cerr << '\n';
    // }
    return dp[1][n];
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30