Submission #404841

#	Time	Username	Problem	Language	Result	Execution time	Memory
404841		CursedCode	Travelling Merchant (APIO17_merchant)	C++14	0 / 100	1085 ms	311672 KiB

merchant

#include <bits/stdc++.h>

using namespace std;

struct node{
	int place;
	int time;
	int maney;
};
vector<int> adj[5000];
int main(){
	short int n,m,k,i,j,h;
	int b[500][500],s[500][500],v,p,w,dp[500][500],money[500][500];
	int efficent[500];
	cin >> n >> m >> k;
	for(i = 1;i <= n;i++){
		for(j = 1;j <= k;j++){
			cin >> b[i][j] >> s[i][j];
		}
	}
	for(i = 1;i <= m;i++){
		cin >> v >> p >> w;
		dp[v][p] = w;
		adj[v].push_back(p);
	}
	for(i = 1;i <= n;i++){
		for(j = 1;j <= n;j++){
			for(h = 1;h <= n;h++){
				if(dp[i][h] != 0 && dp[h][j] != 0)
				dp[i][j] = min(dp[i][j],dp[i][h] + dp[h][j]);
			}
		}
	}
	for(i = 1;i <= n;i++){
		for(j = 1;j <= n;j++){
			for(h = 1;h <= k;h++){
				if(s[i][h] != -1 && b[j][h] != -1)
				money[i][j] = max(money[i][j],s[j][h] - b[i][h]);
			}
		}
	}
	queue<node>l;
	l.push({1,0,0});
	int ans = 0;
	while(!l.empty()){
		node p;
		p = l.front();
		l.pop();
		for(i = 0;i < adj[p.place].size();i++){
			int kl = (p.maney + money[p.place][adj[p.place][i]])/(p.time+dp[p.place][adj[p.place][i]]);
			if(efficent[adj[p.place][i]] > kl && adj[p.place][i] != -1) continue;
			if(adj[p.place][i] != 1) 
			l.push({adj[p.place][i],p.time+dp[p.place][adj[p.place][i]],p.maney + money[p.place][adj[p.place][i]]});
			else{
				ans = max(ans,kl);
			}
			efficent[adj[p.place][i]] = max(efficent[adj[p.place][i]],kl);
		}
	}
	cout << ans;
}

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:49:15: warning: comparison of integer expressions of different signedness: 'short int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   for(i = 0;i < adj[p.place].size();i++){
      |             ~~^~~~~~~~~~~~~~~~~~~~~

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