From 4b6e6c796afc3e74c7070d4c6fe2c5fd2a3f1487 Mon Sep 17 00:00:00 2001 From: Ta180m Date: Sat, 2 May 2020 12:31:30 -0500 Subject: Create time.cpp --- 2020/January/Gold/time.cpp | 35 +++++++++++++++++++++++++++++++++++ 1 file changed, 35 insertions(+) create mode 100644 2020/January/Gold/time.cpp diff --git a/2020/January/Gold/time.cpp b/2020/January/Gold/time.cpp new file mode 100644 index 0000000..fd3b8cf --- /dev/null +++ b/2020/January/Gold/time.cpp @@ -0,0 +1,35 @@ +#include +using namespace std; + +int m[1001], DP[1001][1001]; +vector 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'; +} -- cgit v1.2.3-70-g09d2