Submission #975566

#	Time	Username	Problem	Language	Result	Execution time	Memory
975566		edogawa_something	Travelling Merchant (APIO17_merchant)	C++17	0 / 100	369 ms	8876 KiB

merchant

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vii;
#define pb push_back
#define S second
#define F first
const ll M=101;
const ll inf=2e18;
ll n,m,k,buy[M][M],sell[M][M],dp[M][M][M],dis[M],c[M][M];
vector<pair<ll,ll>>adj[M];
vii v[M];
bool vis[M];
void bfs(ll x){
  queue<ll>q;
  q.push(x);
  for(int i=0;i<n;i++)
  vis[i]=0,dis[i]=inf;
  dis[x]=0;
  vis[x]=1;
  while(!q.empty()){
    ll node=q.front();
    q.pop();
    for(auto it:v[node]){
      if(!vis[it]){
        vis[it]=1;
        dis[it]=dis[node]+1;
        q.push(it);
      }
    }
  }
}
ll cont(ll x,ll y){
  ll &res=c[x][y];
  if(res>=0)
  return res;
  for(int i=0;i<k;i++){
    if(buy[x][i]>0)
    res=max(res,sell[y][i]-buy[x][i]);
  }
  return res;
}
int main(){
  ios_base::sync_with_stdio(0),cin.tie(0);
  cin>>n>>m>>k;
  for(int i=0;i<n;i++){
    for(int j=0;j<k;j++)
    cin>>buy[i][j]>>sell[i][j];
  }
  for(int i=0;i<n;i++)
  for(int j=0;j<n;j++)
  c[i][j]=-1;
  for(int i=0;i<m;i++){
    ll x,y,z;
    cin>>x>>y>>z;
    x--,y--;
    v[x].pb(y);
  }
  for(int i=0;i<n;i++){
    bfs(i);
    for(int j=0;j<n;j++){
    if(j!=i&&dis[j]<=n)
    adj[i].pb({j,dis[j]});
    }
  }
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      if(i==j)
      dp[i][j][0]=0;
      else
      dp[i][j][0]=-inf;
    }
  }
  for(int time=0;time<n;time++){
    for(int i=0;i<n;i++){
      for(int j=0;j<n;j++){
        for(auto it:adj[j]){
          dp[i][it.F][time+it.S]=max(dp[i][it.F][time+it.S],dp[i][j][time]+cont(j,it.F));
        }
      }
    }
  }
  ll ans=0;
  for(int time=1;time<=n;time++){
    for(int i=0;i<n;i++){
      ans=max(ans,dp[i][i][time]/time);
    }
  }
  cout<<ans<<'\n';
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 21
• Subtask 3: 0 / 33
• Subtask 4: 0 / 34