Submission #1126348

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126348		heavylightdecomp	Mountains (IOI17_mountains)	C++20	0 / 100	0 ms	328 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!!!!!
                dp[l][r] = max(dp[l+1][r], dp[l][uuu] + dp[uuu+1][r-1]);
                uuu = r;
            } else { //i can't be seen so it really don't matter????
                // debug(l); debug(r); debug(uuu);
                dp[l][r] = max(dp[l+1][r], dp[l][uuu] + dp[uuu+1][r]);
            }
        }
    }
    return dp[1][n];
}

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