Seguendo lo spoiler di TheScrasse che considera:
Usare K insetticidi di potenza P e N - K insetticidi di potenza Q è equivalente a usarne N di potenza Q e K di potenza P - Q
Ho fatto questa soluzione ma sbaglia tutti i subtask2 e anche alcuni degli altri subtask:
#include <bits/stdc++.h>
using namespace std;
ifstream in("input.txt");
ofstream out("output.txt");
void soluzione(long long rooms[], long long tot, long long num1, long long num2, long long ucc1, long long ucc2)
{
long long max = 0;
for(int i = 0; i<tot; ++i)
{
in >> rooms[i];
if((rooms[i]/ucc1) > max) max = rooms[i]/ucc1;
}
long long day;
long long min = 0;
long long app;
bool trovato = false;
while(!trovato)
{
long long rim = 0;
day = (min + max)/2;
for(int i = 0; i<tot; ++i)
{
app = rooms[i] - day*ucc1;
if(app < 0) app = 0;
rim += app/ucc2;
if(app%ucc2 != 0) ++rim;
}
if(max-min < 2)
{
trovato = true;
}else if((rim-(day*num2))>0)
{
min = day;
}else if((rim-(day*num2))<0)
{
max = day;
}else
{
trovato = true;
}
}
out << max;
}
main()
{
long long tot,num1,num2,ucc1,ucc2;
in >> tot >> num1 >> ucc1 >> ucc2;
num2 = tot - num1;
long long rooms[tot];
if(ucc1 < ucc2)
{
long long app;
app = num1;
num1 = num2;
num2 = app;
app = ucc1;
ucc1 = ucc2;
ucc2 = app;
}
soluzione(rooms, tot, tot, num1, ucc2, ucc1-ucc2);
}