Omówienie zadania Aquapark / Finał III edycji Olimpiady Informatycznej Juniorów

Omówienie zadania Aquapark / Finał III edycji Olimpiady Informatycznej Juniorów

Szczegółowe omówienie zadania Aquapark z finału Olimpiady Informatycznej Juniorów (III edycja):

Link do zadania Aquapark:
https://tiny.pl/tz917
Zadanie pokazuje sumy prefiksowe dwuwymiarowe + wymaga innego spojrzenia na podany w zadaniu basen.
——-
Kod C++ programu Aquapark, który jest omówiony w powyższym filmie

#include <bits/stdc++.h>
using namespace std;

const int MAX_BOK = 1e3+7;
int basen[MAX_BOK][MAX_BOK];
int basen_45stopni[2*MAX_BOK][2*MAX_BOK];
long long int prefix_sum[2*MAX_BOK][2*MAX_BOK];

int main() {
 ios_base::sync_with_stdio(0);
 cin.tie(0);
 cout.tie(0);

 int bok_basenu, liczba_ratownikow;
 int bok_basenu_wydluzony;
 int ratownik_x, ratownik_y, ratownik_zasieg;
 int ratownik_x_45, ratownik_y_45;
 int rog_lewy_gorny_x, rog_lewy_gorny_y;
 int rog_prawy_dolny_x, rog_prawy_dolny_y;
 long long int wynik;
 int x, y;
 int i;

 cin >> bok_basenu >> liczba_ratownikow;
 bok_basenu_wydluzony = 2*bok_basenu+5;
 
 for (y=1; y<=bok_basenu; ++y) {
    for (x=1; x<=bok_basenu; ++x) {
       cin >> basen[x][y];
    }
 }
 
 for (y=1; y<=bok_basenu; ++y) {
    for (x=1; x<=bok_basenu; ++x) {
       basen_45stopni[x-y+bok_basenu+1][x+y+1] = basen[x][y];
    }
 }
 for (y=1; y<=bok_basenu_wydluzony; ++y) {
    for (x=1; x<=bok_basenu_wydluzony; ++x) {
       prefix_sum[x][y] = prefix_sum[x-1][y] + prefix_sum[x][y-1] - prefix_sum[x-1][y-1] +  (long long)basen_45stopni[x][y];
    }
 }

 for (i=1; i<=liczba_ratownikow; ++i) {
 	cin >> ratownik_y >> ratownik_x >> ratownik_zasieg;
 	ratownik_x_45 = ratownik_x - ratownik_y + bok_basenu+1;
 	ratownik_y_45 = ratownik_x + ratownik_y+1;
    rog_prawy_dolny_x = min (ratownik_x_45 + ratownik_zasieg, bok_basenu_wydluzony-1);
    rog_prawy_dolny_y = min (ratownik_y_45 + ratownik_zasieg, bok_basenu_wydluzony-1);
    rog_lewy_gorny_x = max (ratownik_x_45 - ratownik_zasieg, 1);
    rog_lewy_gorny_y = max (ratownik_y_45 - ratownik_zasieg, 1);
    wynik = prefix_sum[rog_prawy_dolny_x][rog_prawy_dolny_y] 
	        - prefix_sum[rog_lewy_gorny_x-1][rog_prawy_dolny_y]
	        - prefix_sum[rog_prawy_dolny_x][rog_lewy_gorny_y-1]
	        + prefix_sum[rog_lewy_gorny_x-1][rog_lewy_gorny_y-1];
	cout << wynik << "\n";
 }
 return 0;
}
Link do pliku z kodem C++ zadania "Aquapark" 

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz