QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #268776 | #7753. Energy Distribution | FISHER_ | WA | 0ms | 3948kb | C++20 | 1.3kb | 2023-11-28 21:02:25 | 2023-11-28 21:02:25 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int maxn = 10;
int w[maxn + 5][maxn + 5];
double m[maxn + 5][maxn + 5], x[maxn + 5];
void gauss(int n) {
for (int i = 0; i <= n; i++) {
double mx = 0; int id;
for (int j = i; j <= n; j++)
if (abs(m[j][i]) > mx) mx = abs(m[j][i]), id = j;
if (mx == 0) continue;
swap(m[i], m[id]);
for (int j = 0; j <= n; j++)
if (i != j) {
double v = m[j][i] / m[i][i];
for (int k = 0; k <= n + 1; k++) m[j][k] -= m[i][k] * v;
}
}
for (int i = 0; i <= n; i++) x[i] = m[i][n + 1] / m[i][i];
}
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) scanf("%d", &w[i][j]);
int S = 1 << n;
double ans = 0;
for (int s = 1; s < S; s++) {
for (int i = 0; i <= n; i++) {
x[i] = 0;
for (int j = 0; j <= n + 1; j++) m[i][j] = 0;
}
for (int i = 0; i < n; i++)
if ((s >> i) & 1) {
for (int j = 0; j < n; j++)
if (i != j && ((s >> j) & 1)) m[i][j] = w[i][j];
m[i][n] = -1, m[n][i] = 1;
}
m[n][n + 1] = 1;
gauss(n);
double sum = 0;
for (int i = 0; i < n; i++)
if (0 > x[i] || x[i] > 1) goto ed;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++) sum += x[i] * x[j] * w[i][j];
ans = max(ans, sum);
ed:;
}
printf("%.7lf", ans);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3880kb
input:
2 0 1 1 0
output:
0.2500000
result:
ok found '0.2500000', expected '0.2500000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
3 0 2 1 2 0 2 1 2 0
output:
0.5714286
result:
ok found '0.5714286', expected '0.5714290', error '0.0000004'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3948kb
input:
3 0 1 2 1 0 1 2 1 0
output:
0.5000000
result:
ok found '0.5000000', expected '0.5000000', error '0.0000000'
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3880kb
input:
4 0 3 1 0 3 0 1 0 1 1 0 2 0 0 2 0
output:
0.4285714
result:
wrong answer 1st numbers differ - expected: '0.7500000', found: '0.4285714', error = '0.3214286'