oj.uz

답안 #135001

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
135001 2019-07-23T14:03:23 Z wzy 여행하는 상인 (APIO17_merchant) C++11
12 / 100
 147 ms 1912 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
const int K = 1005;
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define mp make_pair
typedef long long ll;
int n , m , k;
ll b[N][K] , s[N][K];
ll dist[N][N];
int32_t main(){
	scanf("%d%d%d" , &n , &m , &k);
	for(int i = 0 ; i < n; i++){
		for(int j = 0 ; j < k ; j++){
			scanf("%lld%lld" , &b[i][j], & s[i][j]);
			if(b[i][j] == -1){
				b[i][j] = (ll) 1e9 + (ll) 1e9;
			}
			if(s[i][j] == -1){
				s[i][j] = - (ll) 1e9 - (ll) 1e9;
			}
		}
	}
	for(int i = 0 ; i < N ; i ++){
		for(int j = 0 ; j < N ; j ++ ){
			dist[i][j] = (ll) 1e15;
		}
		dist[i][i] = 0;
	}
	for(int i = 0 ; i < m ; i ++){
		int  u , v, x;
		scanf("%d%d%d" , &u , & v  , &x);
		u-- , v--;
		assert(u >= 0 && v >= 0);
		dist[u][v] = min(dist[u][v] , (ll) x);
	}
	for(int i = 0 ; i < n; i ++ ){
		for(int j = 0 ; j < n ; j ++){
			for(int kx = 0 ; kx < n ; kx ++){
				dist[j][kx] = min(dist[j][i] + dist[i][kx] , dist[j][kx]);
			}
		}
	}
	long long int ans = 0;
	for(int i = 0 ; i < n; i ++){
		for(int j = 0 ; j < n ; j ++){
			if(j == i) continue;
			long long int U = dist[i][j] + dist[j][i];
			for(int x = 0 ; x < k ; x++){
				long long int C = -b[i][x] + s[j][x];
				ans = max(ans , C/U);
			}
		}
	}
	cout<<ans<<endl;
}

Compilation message

merchant.cpp: In function 'int32_t main()':
merchant.cpp:15:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d" , &n , &m , &k);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:18:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%lld%lld" , &b[i][j], & s[i][j]);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:35:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d" , &u , & v  , &x);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 147 ms 1912 KB Output is correct
2 Correct 4 ms 1276 KB Output is correct
3 Correct 4 ms 1144 KB Output is correct
4 Correct 3 ms 760 KB Output is correct
5 Correct 3 ms 760 KB Output is correct
6 Correct 3 ms 760 KB Output is correct
7 Correct 5 ms 808 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 748 KB Output is correct
10 Correct 3 ms 888 KB Output is correct
11 Correct 3 ms 760 KB Output is correct
12 Correct 2 ms 504 KB Output is correct
13 Correct 5 ms 888 KB Output is correct

Subtask #2
0 / 21.0

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

Subtask #3
0 / 33.0

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

Subtask #4
0 / 34.0

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