結果
問題 | No.2953 Maximum Right Triangle |
ユーザー | daiota |
提出日時 | 2024-11-08 23:17:14 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,105 bytes |
コンパイル時間 | 1,835 ms |
コンパイル使用メモリ | 167,556 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-08 23:17:19 |
合計ジャッジ時間 | 2,181 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | WA | - |
testcase_02 | WA | - |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | AC | 2 ms
5,248 KB |
testcase_06 | AC | 2 ms
5,248 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> P; #define REP(i,n) for(int i=0;i<int(n);i++) ll extgcd(ll a,ll b,ll & x,ll & y){ ll g; if(b!=0){ g=extgcd(b,a%b,y,x); y-=(a/b)*x; }else{ g=a; x=1; y=0; } return g; } int main(void){ cin.tie(nullptr); ios_base::sync_with_stdio(false); ll i,j; int T; cin >> T; while(T--){ ll D,a,b; cin >> D >> a >> b; if(a==0){ cout << b*D << endl; continue; } if(b==0){ cout << a*D << endl; continue; } ll x,y; ll c=a*a+b*b; ll g=extgcd(a,b,x,y); if(c%g!=0){ cout << 0 << endl; continue; } ll p=(-c*x/g+b/g-1)/(b/g),q=(D-c*x/g)/(b/g); ll qq=(c*y/g)/(a/g),pp=(c*y/g-D+a/g-1)/(a/g); if(max(p,pp)>min(q,qq)){ cout << 0 << endl; continue; } ll u=max(p,pp),v=min(q,qq); ll X,Y,s,S; X=c*x/g+b*u/g; Y=c*y/g-a*u/g; s=2*max(a,X)*max(b,Y)-(a*b+X*Y+llabs(X-a)*llabs(Y-b)); X=c*x/g+b*v/g; Y=c*y/g-a*v/g; S=2*max(a,X)*max(b,Y)-(a*b+X*Y+llabs(X-a)*llabs(Y-b)); cout << max(s,S) << endl; } return 0; }