#325099 (C++11) No.800 四平方定理

• 問題: No.800 四平方定理
• ユーザー: apoanzan
• 提出日時: 2019-03-17 22:41:52
• 言語: C++11 (gcc 11.4.0)
• 結果: TLE
• 実行時間: -
• コード長: 876 bytes
• コンパイル時間: 1,435 ms
• コンパイル使用メモリ: 169,472 KB
• 実行使用メモリ: 69,292 KB
• 最終ジャッジ日時: 2024-07-08 00:57:28
• 合計ジャッジ時間: 28,128 ms
• ジャッジサーバーID （参考情報）: judge5 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	15 ms; 10,624 KB
testcase_01	AC	28 ms; 5,504 KB
testcase_02	AC	22 ms; 5,376 KB
testcase_03	AC	23 ms; 5,376 KB
testcase_04	AC	20 ms; 5,376 KB
testcase_05	AC	22 ms; 5,376 KB
testcase_06	AC	33 ms; 5,800 KB
testcase_07	AC	25 ms; 5,376 KB
testcase_08	AC	25 ms; 5,932 KB
testcase_09	AC	32 ms; 5,524 KB
testcase_10	AC	1,990 ms; 57,740 KB
testcase_11	AC	1,913 ms; 69,108 KB
testcase_12	AC	1,930 ms; 68,968 KB
testcase_13	AC	1,862 ms; 60,256 KB
testcase_14	AC	1,897 ms; 69,104 KB
testcase_15	TLE	-
testcase_16	TLE	-
testcase_17	TLE	-
testcase_18	TLE	-
testcase_19	TLE	-
testcase_20	AC	2 ms; 5,376 KB
testcase_21	AC	1 ms; 5,376 KB
testcase_22	TLE	-
testcase_23	TLE	-
testcase_24	--	-
testcase_25	--	-
testcase_26	--	-
testcase_27	--	-
testcase_28	--	-
testcase_29	--	-
testcase_30	--	-
testcase_31	--	-
testcase_32	--	-

ソースコード

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

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define mp make_pair
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define MOD 1000000007

map<int,int> B;
vector<int> A;
int ans,cnt;
int main(){
	int N,D;
	cin >> N >> D;
	for(int i = 1;i<N+1;++i){
		for(int j = 1;j<N+1;++j){
			A.pb(D-i*i+j*j);
			B[D-i*i+j*j]++;
		}
	}
	sort(A.begin(),A.end());

	for(int i = 1;i <N+1;++i){
		for(int j=1;j<N+1;++j){
			if(binary_search(A.begin(),A.end(),i*i+j*j)){
			/*	cout <<"upp: " <<*upper_bound(A.begin(),A.end(),i*i+j*j)<<endl;
				cout <<"low: " <<*lower_bound(A.begin(),A.end(),i*i+j*j)<<endl;
				ans += *upper_bound(A.begin(),A.end(),i*i+j*j)-*lower_bound(A.begin(),A.end(),i*i+j*j)+1;*/
				if(B[i*i+j*j]>=1) cnt += B[i*i+j*j];
			}
		}
	}
	cout << cnt <<endl;
	return 0;
}