oj.uz

답안 #945249

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
945249 2024-03-13T15:04:47 Z TAhmed33 여행하는 상인 (APIO17_merchant) C++
0 / 100
 39 ms 2392 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1e16;
const int MAXN = 1e3 + 25;
vector <int> adj[MAXN];
vector <ll> dd[MAXN];
int n, m, k;
ll get () {
	bool vis[n + 1];
	queue <int> cur; cur.push(1); memset(vis, false, sizeof(vis));
	ll dist[n + 1] = {}; vis[1] = 1;
	while (!cur.empty()) {
		int l = cur.front(); cur.pop();
		for (auto j : adj[l]) {
			if (!vis[j]) {
				vis[j] = 1; dist[j] = dist[l] + 1;
				cur.push(j);
			}
		}
	}
	ll tot = inf;
	for (int j = 1; j <= n; j++) {
		if (!vis[j]) continue;
		for (auto k : adj[j]) {
			if (dist[j] == dist[k]) tot = min(tot, 2 * dist[j] + 1);
		}
	}
	for (int j = 1; j <= n; j++) {
		if (!vis[j]) continue;
		int s = 0;
		for (auto k : adj[j]) {
			if (k == 1) continue;
			if (dist[k] == dist[j] - 1) s++;
		}
		if (s > 1) tot = min(tot, 2 * (dist[j] - 1) + 2);
	}
	return tot == inf ? -1 : tot;
}
int main () {
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) {
		dd[i].resize(k);
		for (auto &j : dd[i]) {
			ll x, y; cin >> x >> y;
			j = y - x;
		}
	}
	sort(dd[1].begin(), dd[1].end());
	ll x = get();
	if (x == -1) {
		cout << "0\n";
		return 0;
	}
	reverse(dd[1].begin(), dd[1].end());
	ll mx = 0, sum = 0;
	for (int i = 0; i < (int)dd[1].size(); i++) {
		sum += dd[1][i];
		mx = max(mx, sum / (x * (i + 1)));
	}
	cout << mx << '\n';
}

Subtask #1
0 / 12.0

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

Subtask #2
0 / 21.0

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

Subtask #3
0 / 33.0

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

Subtask #4
0 / 34.0

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