| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1116329 | whale_island1 | Koala Game (APIO17_koala) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// __________________
// | ________________ |
// || ____ ||
// || /\ | ||
// || /__\ | ||
// || / \ |____ ||
// ||________________||
// |__________________|
// \###################\
// \###################\
// \ ____ \
// \_______\___\_______\
// An AC a day keeps the doctor away.
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define hutao_my_wife ios_base::sync_with_stdio(0);
#define forcalors_so_cute cin.tie(0);
/*
inline char readchar() noexcept {
static char buffer[BUFSIZ], * now = buffer + BUFSIZ, * end = buffer + BUFSIZ;
if (now == end)
{
if (end < buffer + BUFSIZ)
return EOF;
end = (buffer + fread(buffer, 1, BUFSIZ, stdin));
now = buffer;
}
return *now++;
}
inline int nextint() noexcept {
int x = 0, c = readchar(), neg = 0;
while(('0' > c || c > '9') && c!='-' && c!=EOF) c = readchar();
if(c == '-') neg = true, c = readchar();
while('0' <= c && c <= '9') x = (x<<3) + (x<<1) + (c^'0'), c = readchar();
if(neg) x = -x;
return x; // returns 0 if EOF
}
//fast io cin>>a 改成 a = nextint();
*/
#define ll long long
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define pb push_back
#define eb emplace_back
#define ALL(v) v.begin(), v.end()
#define bug(A) cout<<A<<" hi\n";
using namespace std;
const ll M = 200005;
int g[105][105];
int B[105][1005], S[105][1005], dis[105][105], earn[105][105];
pii dp[105][105];
int n,m,num;
void solve(){
cin>>n>>m>>num;
for(int i = 1; i <= n; i++){
for(int j = 0; j < num; j++){
cin>>B[i][j]>>S[i][j];
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j ++){
if(i==j)dis[i][j] = 0;
else
dis[i][j] = 1e9+1;
}
}
for(int i = 0; i <m; i++){
int t1,t2,t3;
cin>>t1>>t2>>t3;
dis[t1][t2] = t3;
}
for(int k = 1; k <= n; k++){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
}
}
// for(int i = 1; i <= n; i++){
// for(int j = 1; j <= n; j ++){cout<<dis[i][j]<<' ';}cout<<'\n';}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
earn[i][j] = 0;
for(int l = 0; l < num; l++){
if(S[j][l]==-1||B[i][l] == -1)continue;
earn[i][j] = max(earn[i][j], S[j][l] - B[i][l]);
}
// cout<<i<<' '<<j<<' '<<earn[i][j]<<" shit\n";
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
dp[i][j] = {earn[i][j],dis[i][j]};
}
}
for(int k = 1; k <= n; k++){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if((dp[i][k].ss + dp[k][j].ss) == 0||(dp[i][k].ss + dp[k][j].ss) >= 1e9+1)continue;
if(dp[i][j].ss == 0 || dp[i][j].ff*(dp[i][k].ss+dp[k][j].ss) < (dp[i][k].ff + dp[k][j].ff)*dp[i][j].ss){
dp[i][j] = {(dp[i][k].ff + dp[k][j].ff) , (dp[i][k].ss + dp[k][j].ss)};
}
}
}
}
int ans = 0;;
for(int i = 1; i <= n; i++){
if(dp[i][i].ss==0)continue;
ans = max((int)(dp[i][i].ff / dp[i][i].ss),ans);
}
cout<<ans<<'\n';
}
signed main(){
// hutao_my_wife forcalors_so_cute
int t = 1;
//cin>>t;
while(t--){
solve();
}
return 0;
}
/*
4 5 2
100 100 -1 -1
100 100 -1 -1
100 100 -1 -1
100 100 -1 -1
1 2
*/