| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1228196 | cpdreamer | Land of the Rainbow Gold (APIO17_rainbow) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
const long long INF = 1e17;
typedef long long ll;
const ll MOD = 1000002022;
#define F first
#define pb push_back
#define S second
#define P pair
#define V vector
#define all(v) v.begin(), v.end()
typedef tree<int,null_type,less<int>,rb_tree_tag, tree_order_statistics_node_update> indexed_multiset;
void file() {
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
}
int k;
ll b[(int)101][1000];
ll s[(int)101][1000];
int state[101];
V<P<int,ll>>adj[(int)101];
ll ans=0;
deque<ll>buy[1000],sell[1000];
deque<ll>dp;
ll di[101];
void dfs(int n,ll d) {
ll x=0;
for (int i=0;i<k;i++) {
ll y=s[n][i];
ll z=-INF;
for (int j=(int)buy[i].size()-1;j>=0;j--) {
ll a=-buy[i][j];
if (j>=1) {
a+=dp[j-1];
}
z=max(z,a);
}
y+=z;
x=max(x,y);
}
if ((int)dp.size()>0) {
x=max(x,dp[(int)dp.size()-1]);
}
if (state[n]==1) {
ans=max(ans,x/(d-di[n]));
return;
}
di[n]=d;
state[n]=1;
dp.push_back (x);
for (int i=0;i<k;i++) {
buy[i].pb(b[n][i]);
sell[i].pb(b[n][i]);
}
for (auto [u,w]:adj[n]) {
dfs(u,d+w);
}
state[n]=2;
for (int i=0;i<k;i++) {
buy[i].pop_back();
sell[i].pop_back();
}
dp.pop_back();
}
void solve() {
int n,m;
cin>>n>>m>>k;
for (int i=1;i<=n;i++) {
for (int j=0;j<k;j++) {
cin>>b[i][j]>>s[i][j];
if (b[i][j]==-1) {
b[i][j]=INF;
}
if (s[i][j]==-1) {
s[i][j]=-INF;
}
}
}
for (int i=1;i<=n;i++) {
state[i]=0;
}
for (int i=0;i<m;i++) {
int a,b;
ll w;
cin>>a>>b>>w;
adj[a].pb({b,w});
}
for (int i=1;i<=n;i++) {
if (state[i]==0) {
dfs(i,0);
}
}
cout<<ans<<endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
//file();
solve();
}