Submission #1210729

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210729		qwusha	Radio Towers (IOI22_towers)	C++20	11 / 100	4093 ms	1980 KiB

towers

#include <bits/stdc++.h>
#include "towers.h"
using namespace std;
#define fi first
#define se second
typedef long long ll;
typedef long double ld;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
ll inf = 1e18;

int n;
vector<int> h;

void init(int N, vector<int> H) {
    n = N;
    h = H;
}

int max_towers(int l, int r, int d) {
    vector<pair<int, int>> dp(n, {1, 0});
    int res = 0;
    for (int i = l; i <= r; i++) {
        for (int j = l; j < i; j++) {
            if (h[j] + d <= h[i]) {
                dp[i].se = max(dp[i].se, dp[j].fi);
            } 
            if (h[i] + d <= h[j]) {
                dp[i].fi = max(dp[j].se + 1, dp[i].fi);
            }
        }
        res = max(res, dp[i].fi);
    }
    return res;
}

• Subtask 1: 0 / 4
• Subtask 2: 11 / 11
• Subtask 3: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 17
• Subtask 6: 0 / 19
• Subtask 7: 0 / 23