Cześc przerabiam właśnie zadanie z 3 etapu OIG-a link szkopul:
https://szkopul.edu.pl/problemset/problem/ocGBMr4-sFMy6iEUQ6cZ6gNW/site/?key=statement
Wydaje mi się to zadanie dość proste, jednak dostaję dla wszystkich testów oprócz tych testowych 0pkt.
Dla każdego wielokąta obliczam pitagorasem maksymalny promień wszystkich wierzchołków(minimalny promień, aby pokryć cały wielokąt) Sortuję ję i sprawdzam cene biorąc pod uwagę elementy składające się z 1 potem 1,2 potem 1,2,3 domów itd i biorę mina. Wiem, że moja aktualna złożonnośc to kwadratowa i mogę przyśpieszyć do O(1) liczenie sumy zysku wszystkich nagród sumami prefiksowymi. Jednak narazie chcę zrobić, żeby algorytm działał.
Mój kod:
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
struct Wielokat
{
long long nagroda;
long long potrzebny_promien;
bool operator < (const Wielokat&wielokat) const
{
return potrzebny_promien < potrzebny_promien;
}
};
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n = 0;
int k = 0;
int wczytana_nagroda = 0;
int wczytana_liczba_wierzcholkow = 0;
long long wczytane_x = 0;
long long wczytane_y = 0;
double min_promien = 0;
double odleglosc = 0;
long long max_zysk = 0;
long long zysk = 0;
long long zasieg = 0;
vector<Wielokat> wielokaty;
cin >> n >> k;
for (int i = 0; i < n; ++i)
{
cin >> wczytana_liczba_wierzcholkow >> wczytana_nagroda;
min_promien = 0;
for (int j = 0; j < wczytana_liczba_wierzcholkow; ++j)
{
cin >> wczytane_x >> wczytane_y;
odleglosc = sqrt(pow(wczytane_x,2) + pow(wczytane_y,2));
min_promien = max(min_promien,odleglosc);
}
wielokaty.push_back({wczytana_nagroda,ceil(min_promien)});
}
sort(wielokaty.begin(),wielokaty.end());
/*
for (auto i : wielokaty)
{
cout << "Nagroda: " << i.nagroda << " potrzebny promien: " << i.potrzebny_promien << endl;
}
cout << endl;
*/
for (int i = 0; i < n; ++i)
{
// Najpierw zlozonnosc kwadratowa dla testu czy ok, potem easy do logarytmicznej.
zysk = 0;
for (int j = 0; j <= i; ++j)
{
zysk += wielokaty[j].nagroda; // Tu mozna sumy prefiksowe.
}
if (wielokaty[i].potrzebny_promien % k != 0)
{
zasieg = (wielokaty[i].potrzebny_promien / k) * k + k;
}
else
{
zasieg = wielokaty[i].potrzebny_promien;
}
long long ile_razy_zwiekszyc = zasieg / k;
long long koszt_utrzymania = (0 + ile_razy_zwiekszyc-1) * (ile_razy_zwiekszyc) / 2; // Suma ciagu od 0 do ile_razy_zwiekszyc -1
zysk -= koszt_utrzymania;
cout << "Koszt utrzymania: " << koszt_utrzymania << endl;
cout << "Potrzebny zasieg: " << zasieg << endl;
cout << "Zysk: " << zysk << endl;
cout << endl;
max_zysk = max(max_zysk,zysk);
}
cout << max_zysk;
return 0;
}
Z góry dziękuję za wszystkie odpowiedzi!