Submission #852870

#	Time	Username	Problem	Language	Result	Execution time	Memory
852870		anha3k25cvp	Mountains (IOI17_mountains)	C++14	100 / 100	23 ms	16220 KiB

mountains

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define dl double
#define st first
#define nd second
#define II pair <int, int>
#include "mountains.h"

using namespace std;

struct Node {
    ll x, y;
    bool operator <(const Node &O) const {
        return x * O.y - y * O.x >= 0;
    }
};

int maximum_deevs(vector<int> y) {
    int n = y.size();
    y.resize(n + 1);
    for (int i = n; i > 0; i --)
        y[i] = y[i - 1];
    vector <vector <int>> f(n + 1, vector <int> (n + 1, 0));
    for (int r = 1; r <= n; r ++) {
        f[r][r] = 1;
        int last = r, sum = 0;
        for (int l = r - 1; l > 0; l --) {
            Node u = {last - l, y[last] - y[l]}, v = {r - l, y[r] - y[l]};
            if (u < v) {
                sum += f[l + 1][last - 1];
                last = l;
            }
            f[l][r] = max(f[l][r - 1], f[l][last - 1] + sum + 1);
        }
    }
	return f[1][n];
}

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