Submission #58134

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
58134	2018-07-17T00:36:47 Z	Benq	Skyline (IZhO11_skyline)	C++14	100 / 100	270 ms	63916 KB

skyline

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

bool done[301][201][201];
int val[301][201][201];
int n,h[303];

void tri(int& a, int b) { a = min(a,b); }

int get(int pos, int h1, int h2) {
    if (pos == n+1) return 0;
    if (done[pos][h1][h2]) return val[pos][h1][h2];
    done[pos][h1][h2] = 1;
    val[pos][h1][h2] = MOD;
    if (h1) {
        tri(val[pos][h1][h2],get(pos,h1-1,h2)+3);
        if (h2) {
            tri(val[pos][h1][h2],get(pos,h1-1,h2-1)+5);
            if (h1 <= min(h2,h[pos+2])) tri(val[pos][h1][h2],get(pos+1,h2-h1,h[pos+2]-h1)+7*h1);
        }
    } else val[pos][h1][h2] = get(pos+1,h2,h[pos+2]);
    return val[pos][h1][h2];
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    FOR(i,1,n+1) cin >> h[i];
    cout << get(1,h[1],h[2]);
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	504 KB	Output is correct
2	Correct	3 ms	624 KB	Output is correct
3	Correct	3 ms	732 KB	Output is correct
4	Correct	4 ms	1996 KB	Output is correct
5	Correct	2 ms	1996 KB	Output is correct
6	Correct	3 ms	1996 KB	Output is correct
7	Correct	4 ms	1996 KB	Output is correct
8	Correct	4 ms	1996 KB	Output is correct
9	Correct	5 ms	2048 KB	Output is correct
10	Correct	6 ms	3588 KB	Output is correct
11	Correct	29 ms	16268 KB	Output is correct
12	Correct	13 ms	16268 KB	Output is correct
13	Correct	43 ms	18296 KB	Output is correct
14	Correct	48 ms	24980 KB	Output is correct
15	Correct	144 ms	51812 KB	Output is correct
16	Correct	148 ms	51812 KB	Output is correct
17	Correct	196 ms	63904 KB	Output is correct
18	Correct	207 ms	63904 KB	Output is correct
19	Correct	270 ms	63904 KB	Output is correct
20	Correct	234 ms	63916 KB	Output is correct