Ktoś to liczył na bieżąco? Mi stablicowanie wyników zajęło jakieś 140s.

Preprocessing, który na moim kompie mi zajmował 2.2s na SIO dostawał TLE przy 10s, więc stablicowałem xd

Obliczam:
(1) Liczbę dowolnych trójek a,b,c takich, że a^2+b^2+c^2<=n^2
(2) Liczbę trójek a,b,c z warunkiem a=b
Na koniec muszę przeliczyć to na właściwy wynik - liczbę trójek a<b<c zliczyłam 6x w (1) a ma ich być 3x. Liczbę trójek a=b!=c zliczyłam 3x w (1) a ma ich być 2x.

Do obliczenia (1):
- obliczam t[x] = liczba par a,b : takich, że a^2+b^2 = x (znajdowane w n^2)
- wynik = wybieram przekątną k i jeden z boków a, czyli sumuję t[k*k - a*a] (znajdowane w n^2)

Obliczam (2) analogicznie do (1). t[x] zlicza a^2+a^2 = x czyli trochę overkill ale nie lubię pierwiastków :)

Max czas na SIO 0.41s.

To samo co Ania, tylko licząc t[x] po prostu wymuszam a<=b, więc nie mam kejsu (2).

Rozwiązanie O(n^2):

#include <iostream>
using namespace std;

int freq[5000 * 5000 + 5000 * 5000 + 1] = { 0 };
int count_solutions_fast(int n) {
for (int a = 1; a <= n; a++) {
for (int b = a; b <= n; b++) {
int s = a * a + b * b;
freq[s]++;
}
}

int count = 0;
for (int c = 1; c <= n; c++) {
for (int d = c; d <= n; d++) {
count += freq[d * d - c * c];
}
}

return count;
}

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

int n;
cin >> n;

int result = count_solutions_fast(n);
cout << result;

return 0;
}

Miałem identyczny pomysł jak kolega powyżej:
#include<bits/stdc++.h>
using namespace std;
const int N = 5001;
int n,DP[N*N];
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

cin >> n;
long long res = 0;
for(int i = 1;i <= n;i++)
for(int j = i;i*i + j*j <= n*n;j++)
DP[i*i + j*j]++;
for(int i = 1;i <= n;i++){
for(int j = i-1;j > 0;j--){
res += DP[i*i - j*j];
}
}
cout << res << "\n";
}