oj.uz

답안 #975567

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
975567 2024-05-05T13:30:34 Z edogawa_something 여행하는 상인 (APIO17_merchant) C++17
0 / 100
 391 ms 8872 KB 
#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 time=0;time<=n;time++){
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      if(i==j&&time==0)
      dp[i][j][0]=0;
      else
      dp[i][j][time]=-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.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 11 ms 1116 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 137 ms 4784 KB Output is correct
2 Correct 79 ms 4700 KB Output is correct
3 Incorrect 335 ms 4700 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 391 ms 8872 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 137 ms 4784 KB Output is correct
2 Correct 79 ms 4700 KB Output is correct
3 Incorrect 335 ms 4700 KB Output isn't correct
4 Halted 0 ms 0 KB -