oj.uz

Submission #73355

# Submission time Handle Problem Language Result Execution time Memory
73355 2018-08-28T07:48:47 Z FedericoS Travelling Merchant (APIO17_merchant) C++14
12 / 100
 100 ms 2868 KB 
#include <iostream>
using namespace std;

int INF=1e9;
int N,M,K;
int x,y;
int C[100][1005][2];
int D[105][105];
int P[105][105];

int main(){

	cin>>N>>M>>K;
	for(int i=0;i<N;i++)
		for(int j=0;j<K;j++)
			cin>>C[i][j][0]>>C[i][j][1];

	for(int i=0;i<N;i++)
		for(int j=0;j<N;j++)
			D[i][j]=(i==j)?0:INF;

	for(int i=0;i<M;i++)
		cin>>x>>y>>D[x-1][y-1];

	for(int k=0;k<N;k++)
		for(int i=0;i<N;i++)
			for(int j=0;j<N;j++)
				D[i][j]=min(D[i][j],D[i][k]+D[k][j]);

	for(int a=0;a<N;a++)
		for(int b=0;b<N;b++)
			for(int j=0;j<K;j++)
				if(C[a][j][0]!=-1 and C[b][j][1]!=-1)
					P[a][b]=max(P[a][b],C[b][j][1]-C[a][j][0]);

	int ans=0;
	for(int i=1;i<N;i++)
		ans=max(ans,(P[0][i]+P[i][0])/(D[0][i]+D[i][0]));

	cout<<ans;

}
	/*for(int a=0;a<N;a++)
		for(int b=0;b<N;b++)
			cout<<a<<" "<<b<<" "<<P[a][b]<<endl;*/

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 2376 KB Output is correct
2 Correct 5 ms 2376 KB Output is correct
3 Correct 4 ms 2376 KB Output is correct
4 Correct 2 ms 2376 KB Output is correct
5 Correct 3 ms 2376 KB Output is correct
6 Correct 4 ms 2376 KB Output is correct
7 Correct 5 ms 2376 KB Output is correct
8 Correct 4 ms 2376 KB Output is correct
9 Correct 3 ms 2376 KB Output is correct
10 Correct 4 ms 2376 KB Output is correct
11 Correct 4 ms 2376 KB Output is correct
12 Correct 3 ms 2376 KB Output is correct
13 Correct 6 ms 2376 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 2868 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -