이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair <ll, ll>
#define ff first
#define ss second
#define sz size()
const int N = 1e2 + 5;
const int K = 1e3 + 5;
ll baha[N], vis[N], buy[N][K], sell[N][K], n, m, d, dis[N][N], profit[N][N];
vector <ll> nodes;
vector <pii> v[N];
ll node, val, new_jog;
ll ugrat () {
ll ret = 0;
for (int i = 1; i < (int)nodes.sz; ++i) {
for (int j = 0; j < i; ++j) {
ll x = nodes[j], y = nodes[i];
baha[i] = max (baha[i], baha[j] + profit[x][y]);
}
ret = max (ret, baha[i]);
}
for (int i = 0; i < (int)nodes.sz; ++i) {
baha[i] = 0;
}
return ret;
}
void dfs (ll x, ll wagt) {
if (vis[x]) {
if (x == node) {
nodes.pb(x);
// for (int i : nodes) {
// cout << i << " ";
// }
// exit(0);
ll jog = ugrat ();
jog -= (val * 1LL * wagt);
if (jog >= 0) new_jog = 1;
nodes.pop_back();
}
return;
}
vis[x] = 1;
nodes.pb (x);
for (pii i : v[x]) {
dfs (i.ff, wagt + (ll)i.ss);
}
vis[x] = 0;
nodes.pop_back();
}
bool check (ll x) {
// jog - x * time >= 0
for (ll i = 1; i <= n; ++i) {
node = i;val = x;
new_jog = 0;
dfs (node, 0);
if (new_jog) return 1;
}
return 0;
}
int main () {
// freopen ("input.txt", "r", stdin);
cin >> n >> m >> d;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= d; ++j) {
cin >> buy[i][j] >> sell[i][j];
}
}
// if (sana == 1) {
cout << "1\n";
return 0;
// }
for (int i = 1; i <= m; ++i) {
ll l, r, w;
cin >> l >> r >> w;
v[l].pb ({r, w});
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (i == j) continue;
for (int k = 1; k <= d; ++k) {
// k-th item-y i-njiden satyn alyan j-nynjyda satyan
if (sell[j][k] != -1 and buy[i][k] != -1)
profit[i][j] = max (profit[i][j], sell[j][k] - buy[i][k]);
}
}
}
// cout << profit[1][2];
// return 0;
ll l = 0, r = 1e9 + 5, jog = 0;
int sana = 0;
while (l <= r) {
ll md = (l + r) / 2;
++sana;
if (sana == 1) {
cout << "1\n";
return 0;
}
if (check (md)) {
jog = md;
l = md + 1;
}
else {
r = md - 1;
}
}
cout << jog;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |