Cześć,
Na themisie mam zadanie, które przechodzi mi w 1 na 2 egzaminy, 2 wywala mi seg fault. Normalnie pddaję się już, nie wiem, o co chodzi.
Treść zadania jest następująca:
Dla danej planszy liczb nieujemnych podaj maksymalną sumę liczb, jaką można zebrać idąc z lewego narożnika (na górze) do prawego (na dole) w taki sposób, że dozwolone są tylko ruchy w dół lub w prawo.
Wejście
W pierwszej linii wejścia dana jest liczba testów. Każdy test rozpoczyna się dwoma liczbami h, w (1 ≤ h, w ≤ 1000) zadającymi liczbę wierszy i kolumn planszy. Następnie dana jest plansza o tychże wymiarach wypełniona liczbami co do modułu nie większymi od miliona.
Wyjście
Dla każdego testu należy wypisać jedną liczbę – odpowiedź zgodną z opisem w zadaniu.
Przykład
Dla danych wejściowych
2
2 3
1 7 9
2 8 4
3 4
1 1 1 1
2 3 1 7
1 1 2 8
poprawną odpowiedzią jest
21
22
Po czy mój kod:
#include <bits/stdc++.h>
using namespace std;
struct TAB
{
int val1, val2, vals, valt;
int tab[1000];
};
int getSum(int BITree[], int index)
{
int sum = 0;
while (index > 0) {
sum = max(sum, BITree[index]);
index -= index & (-index);
}
return sum;
}
void updateBIT(int BITree[], int newIndex,
int index, int val)
{
while (index <= newIndex) {
BITree[index] = max(val, BITree[index]);
index += index & (-index);
}
}
int maxSumIS(int arr[], int n)
{
int newindex = 0, max_sum;
map<int, int> uniqueArr;
for (int i = 0; i < n; i++) {
uniqueArr[arr[i]] = 0;
}
for (map<int, int>::iterator it = uniqueArr.begin();
it != uniqueArr.end(); it++) {
newindex++;
uniqueArr[it->first] = newindex;
}
int* BITree = new int[newindex + 1];
for (int i = 0; i <= newindex; i++) {
BITree[i] = 0;
}
for (int i = 0; i < n; i++) {
max_sum = getSum(BITree, uniqueArr[arr[i]] - 1);
updateBIT(BITree, newindex,
uniqueArr[arr[i]], max_sum + arr[i]);
}
return getSum(BITree, newindex);
}
int main()
{
int num;
cin >> num;
if ((num<1) || (num > 1000))
{
return 0;
}
TAB stokrotki[num];
for(int i = 0; i < num; i++)
{
cin >> stokrotki[i].val1;
cin >> stokrotki[i].val2;
stokrotki[i].vals = stokrotki[i].val1 * stokrotki[i].val2;
stokrotki[i].valt = stokrotki[i].vals + 2;
stokrotki[i].tab[0] = stokrotki[i].val1;
stokrotki[i].tab[1] = stokrotki[i].val2;
for(int j=2; j<stokrotki[i].valt; j++)
{
cin >> stokrotki[i].tab[j];
if((stokrotki[i].tab[j] > 1000000))
{
return 0;
}
}
}
for(int i = 0; i < num; i++)
{
int arr[stokrotki[i].valt];
for(int j=0; j<stokrotki[i].valt;j++)
{
arr[j] = stokrotki[i].tab[j];
}
int n = sizeof(arr) / sizeof(arr[0]);
cout << maxSumIS(arr, n) << endl;
}
return 0;
}
No dla przykładu z zadania śmiga jak złoto - dla sprawdzianu 1 - złoto , ale sprawdzian 2 kicha.
Czy ktoś byłby w stanie wykryć co zrobiłem nie tak i pokazać w którym miejscu należy poprawić?