Terminated due to signal: SEGMENTATION FAULT (11) trên CodeRunner

[Tien_Dung2 (Tien Dzung)]

Hiện tại em đang làm 1 bài trên codeforces bài 505C và cùng 1 code nhưng trên codeforces và ideone đều chạy ngon lành nhưng khi em chạy ở coderunner thì lại ăn lỗi Terminated due to signal: SEGMENTATION FAULT (11) ạ :< mong mọi người giúp em, phần code đây ạ.

#include<bits/stdc++.h>
using namespace std;
const int M = 30001;
int dp[30001][500],gem[M],d;
bool used[30001][500];
int solve(int i, int j) {
	int jj = j-(d-250);
	if (i >= 30001) return 0;
	if (used[i][jj]) return dp[i][jj];
	used[i][jj] = true;
	int res;
	if (j==1) res=gem[i]+max(solve(i+j,j),solve(i+j+1,j+1));
	else res=gem[i]+max(max(solve(i+j-1,j-1), solve(i+j,j)), solve(i+j+1,j+1));
	dp[i][jj]=res;
	return res;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int n;
	cin>>n>>d;
	for (int i=1;i<=n;i++) {
		int x;
		cin>>x;
		gem[x]++;
	}
	cout<<solve(d, d);
	return 0;
}

[Tien_Dung2 (Tien Dzung)]

[NQH (Reisen_1943)]

Cho mình hỏi máy bạn bao nhiêu gb ấy nhỉ ?
PS: Theo mình nghĩ thì do cách khai báo 2 mảng kia là quá lớn:
4 * 30001 * 500 + 1 * 30001 * 500 = 75002500 ~ khoảng 0,7 gb
và chương trình còn có hàm đệ quy thì mình nghĩ với mức ram thấp thì ct dễ đụng tới những vùng nhớ bị giới hạn bởi Kernel.

[Tien_Dung2 (Tien Dzung)]

Máy em Mac Air 2018 RAM là 8GB còn bộ nhớ ổ đĩa thừa tận 92 GB ạ

Em chạy trên con PC ghẻ RAM4GB vẫn chạy đc bthg mà trên con Mac thì bị thế ạ thế là do máy Mac ạ ?

[tntxtnt]

bấm chạy là lỗi hay input rồi mới gặp lỗi? dp và used ngốn có 75MB dư sức chứa được khi khai báo là biến global mà :V

[Tien_Dung2 (Tien Dzung)]

Input xong mới bị lỗi ạ

[tntxtnt]

vậy input là gì :V trong cái hàm solve() ko thấy kiểm tra jj có < 500 hay >= 0 hay ko chắc lỗi ở đây

[Tien_Dung2 (Tien Dzung)]

Dạ, input là:

4 10
10
21
27
27

[Tien_Dung2 (Tien Dzung)]

Em đã tìm được lỗi rồi ạ ở chỗ
else res=gem[i]+max(max(solve(i+j-1,j-1), solve(i+j,j)), solve(i+j+1,j+1));

em thay bằng:

else 
{
	res=max(solve(i+j,j), solve(i+j+1,j+1));
	res=max(res,solve(i+j-1,j-1))+gem[i];
}

Thì lại được mặc dù chả hiểu nó khác gì nhau:(

Điều này thật khó hiểu

[rogp10]

Bạn test max giới hạn đề bài phải ko

[Tien_Dung2 (Tien Dzung)]

Không ạ em thử test cực bé mà lúc đó không chạy đc mà chỉ trên Macbook thôi ạ còn trên PC, hoặc chạy bằng CF vẫn Accepted như bthg ạ

[tntxtnt]

vậy là do undefined behavior gì rồi. f(a, b, c) thì a b c ko được tính theo thứ tự a rồi b rồi c, mà theo thứ tự nào cũng được, abc, acb, bac, … Vì hàm solve() có làm thay đổi dp và used nên lỡ compiler nó dịch ko phải theo thứ tự từ trái sang phải thì có thể gây lỗi. Giống như gọi f(i++, ++i) là undefined behavior vậy đó :V

trong phần sửa rồi vẫn còn undefined behavior kìa: 2 cái solve() truyền vô cùng trong hàm max()
sửa lại là

else 
{
    res = solve(i + j, j);
    res = max(res, solve(i + j + 1, j + 1));
    res = max(res, solve(i + j - 1, j - 1)) + gem[i];
}

hoặc

else
{
    int temp1 = solve(i + j, j);
    int temp2 = solve(i + j + 1, j + 1);
    int temp3 = solve(i + j - 1, j - 1);
    res = gem[i] + max(max(temp1, temp2), temp3);
}

sửa luôn cái if ở trên nữa

if (j == 1)
{
    int temp1 = solve(i + j, j);
    int temp2 = solve(i + j + 1, j + 1);
    res = gem[i] + max(temp1, temp2);
}

[Tien_Dung2 (Tien Dzung)]

Em cảm ơn nhiều ạ

[noname00 (HK boy)]

Logic khác hẳn nhau nhé.

res=gem[i]+max(max(solve(i+j-1,j-1), solve(i+j,j)), solve(i+j+1,j+1));

tức là

res = gem[i] + max(3_cái_solve())

Còn

res=max(solve(i+j,j), solve(i+j+1,j+1)); 
res=max(res,solve(i+j-1,j-1))+gem[i];

tức là

res = max(2_cái_solve(), gem[i] + 1_cái_solve()_khác);

[Tien_Dung2 (Tien Dzung)]

Dạ theo em nghĩ thì không phải là res = max(2_cái_solve(), gem[i] + 1_cái_solve()_khác);
Vì gem[i] nó không thể nằm tronng hàm max đc ạ do code là

res=max(solve(i+j,j), solve(i+j+1,j+1)); 
res=max(res,solve(i+j-1,j-1))+gem[i];

Trong code trên thì gem[i] nó đâu nằm trong hàm max đâu ạ nếu ghi như của a thì nếu 2 cái solve kia lớn hơn 1 cái solve+gem[i] thì tức là mình sẽ chọn 2 cái solve và gem[i] không được thêm vào nhưng theo code của em thì dù như thế nào đi nữa thì gem[i] vẫn sẽ được cộng vào với res

[noname00 (HK boy)]

Mình không nói đến thuật toán của bạn sai hay đúng, mà nói logic bạn nghĩ có đúng như thật sự là như vậy hay không thôi.

Đây, trích lại nguyên văn nhé

ở chỗ
else res=gem[i]+max(max(solve(i+j-1,j-1), solve(i+j,j)), solve(i+j+1,j+1));

em thay bằng:

else 
{
	res=max(solve(i+j,j), solve(i+j+1,j+1));
	res=max(res,solve(i+j-1,j-1))+gem[i];
}

Thì lại được mặc dù chả hiểu nó khác gì nhau:(

---

Trong code trên thì gem[i] nó đâu nằm trong hàm max đâu ạ nếu ghi như của a thì nếu 2 cái solve kia lớn hơn 1 cái solve+gem[i] thì tức là mình sẽ chọn 2 cái solve và gem[i] không được thêm vào nhưng theo code của em thì dù như thế nào đi nữa thì gem[i] vẫn sẽ được cộng vào với res

Ai lấy mất của bạn dấu chấm dấu phẩy sao @@