QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#268261 | #7753. Energy Distribution | SATSKY | WA | 0ms | 3956kb | C++20 | 1.8kb | 2023-11-28 14:28:43 | 2023-11-28 14:28:44 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;const double eps=1e-10;using ll=long long;const int M=998244353;
struct Mat{
int n,m;vector<vector<double>>mat;vector<int>sol;Mat(int _n,int _m){ini(_n,_m);}
void ini(int _n,int _m){n=_n,m=_m,mat.resize(n,vector<double>(m,0));}
int Gauss(){//0:none/1:only sol/2:multi sol
int pt=0;for(int c=0;c<n;c++){
int t=pt;for(int i=pt;i<n;i++)if(abs(mat[i][c])>abs(mat[t][c]))t=i;
if(abs(mat[t][c])<eps)continue;swap(mat[t],mat[pt]);for(int i=m-1;i>=c;i--)mat[pt][i]/=mat[pt][c];
for(int i=0;i<n;i++)if(pt!=i&&abs(mat[i][c])>eps)for(int j=m-1;j>=c;j--)mat[i][j]-=mat[pt][j]*mat[i][c];pt++;}
if(pt==n)return 1;for(int i=pt;i<n;i++)for(int j=n;j<m;j++)if(abs(mat[i][j])>eps)return 0;return 2;}
void outp(){for(int i=0;i<n;i++)for(int j=0;j<m;j++)cout<<mat[i][j]<<" \n"[j==m-1];cout<<"%%%\n";}};
struct S
{
int n;
void solve()
{
cin>>n;vector<vector<int>>a(n,vector<int>(n));for(auto &k:a)for(auto&kk:k)cin>>kk;int B=(1<<n);double mx=0;
for(int k=0;k<B;k++)
{
Mat A(n,n+1);for(int i=0;i<n;A.mat[i++][n]=1)if(k&(1<<i))
for(int j=0;j<n;j++)if((k&(1<<i))&&i!=j)A.mat[i][j]=(i<j)?a[i][j]:a[j][i];
//A.outp();
A.Gauss();
//A.outp();
vector<double>res(n,0);double sum=0;
for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(abs(A.mat[i][j])>eps){res[j]=A.mat[i][n],sum+=res[j];break;}
//for(auto k:res)cout<<k<<'_';cout<<'\n';
if(abs(sum)<eps)continue;for(auto &k:res)k/=sum;sum=0;
for(int i=0;i<n;i++)for(int j=i+1;j<n;j++)sum+=res[i]*res[j]*a[i][j];
mx=max(mx,sum);//cout<<sum<<'\n';
}
cout<<mx<<'\n';
}
};
int main()
{
//freopen("1.in","r",stdin);
cout<<fixed<<setprecision(12);
ios::sync_with_stdio(0);cin.tie(0);
int t=1;/*cin>>t;*/
while(t--){S SS;SS.solve();}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3820kb
input:
2 0 1 1 0
output:
0.250000000000
result:
ok found '0.2500000', expected '0.2500000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
3 0 2 1 2 0 2 1 2 0
output:
0.571428571429
result:
ok found '0.5714286', expected '0.5714290', error '0.0000004'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
3 0 1 2 1 0 1 2 1 0
output:
0.500000000000
result:
ok found '0.5000000', expected '0.5000000', error '0.0000000'
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3956kb
input:
4 0 3 1 0 3 0 1 0 1 1 0 2 0 0 2 0
output:
1.000000000000
result:
wrong answer 1st numbers differ - expected: '0.7500000', found: '1.0000000', error = '0.2500000'