This is the problem: Beach Umbrellas(AIO2020)
Here is my code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define sz(x) (int)(x).size()
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#ifndef DEBUG
freopen("beachin.txt", "r", stdin);
freopen("beachout.txt", "w", stdout);
#endif
int n, u, k, x;
cin >> n >> u >> k >> x;
vector<int> grid(n + 1, 0);
for (int i = 0; i < u; ++i) {
int a, b;
cin >> a >> b;
--a;
grid[a]++;
grid[b]--;
}
int total = 0, cur = 0, best = 0;
for (int i = 0; i < n + 1; ++i) {
total += grid[i];
if (total > 0) {
grid[i] = 1;
++cur;
} else {
grid[i] = 0;
best = max(cur, best);
cur = 0;
}
}
int mx = best;
if (k == 0) cout << best;
else if (x == 1) {
mx += k;
cout << min(n, mx);
} else {
mx += min(k, n - best) * x;
cout << min(n, mx);
}
return 0;
}
My Approach
I attempted to solve this problem by first marking where the initially placed umbrellas are and iterate through the length of the beach. After that, i consider if there are any extra umbrellas i can place, if there is and the size of each is 1, i just add the total size of extra umbrellas to what I have already.
My solution received a 7/100, only solving all the sample cases, subtask 1, and a few test cases from the other subtask
What I need help with
I need help improving the placement algorithm for the umbrellas as currently, when the size of the extra umbrellas are greater than 1, my algorithm only works half the time
Any help will be greatly appreciated.
Thanks.