blob: fd3b8cf399b85e4135d187a5f5915062d82b39f7 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
#include <bits/stdc++.h>
using namespace std;
int m[1001], DP[1001][1001];
vector<int> G[1001];
int main() {
ifstream cin("time.in");
ofstream cout("time.out");
int N, M, C;
cin >> N >> M >> C;
for (int u = 1; u <= N; ++u) cin >> m[u];
while (M--) {
int a, b;
cin >> a >> b;
G[a].push_back(b);
}
memset(DP, -1, sizeof DP);
DP[0][1] = 0;
for (int i = 0; i < 1000; ++i) {
for (int u = 1; u <= N; ++u) {
if (DP[i][u] != -1) {
for (auto& v : G[u]) {
DP[i + 1][v] = max(DP[i][u] + m[v], DP[i + 1][v]);
}
}
}
}
int ans = 0;
for (int i = 1; i <= 1000; ++i) ans = max(DP[i][1] - C * i * i, ans);
cout << ans << '\n';
}
|
