Submission #232065

#	Time	Username	Problem	Language	Result	Execution time	Memory
232065		ChrisT	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	120 ms	2552 KiB

merchant

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
using pib = pair<int,bool>;
using ll = long long;
using ld = long double;
#define all(x) (x).begin(),(x).end()
#ifdef fread_unlocked
#define fread fread_unlocked
#define fwrite fwrite_unlocked
#endif
#define lc ind<<1
#define rc ind<<1|1
const int MN = 103, MOD = 1e9+7, BASE = 31;
vector<pii> adj[MN];
ll dp[MN][MN], dist[MN][MN], d[MN][MN];//start, end
ll buy[MN][MN*10], sell[MN][MN*10], go[MN][MN];
void uin (ll &a, ll b) {if(b<a)a=b;}
int main () { 
	int n,m,K;
	scanf ("%d %d %d",&n,&m,&K);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= K; j++) {
			scanf ("%lld %lld",&buy[i][j],&sell[i][j]);
		}
	}
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			dist[i][j] = i==j?0:1e9;
	while (m--) {
		int a,b,c; scanf ("%d %d %d",&a,&b,&c);
		uin(dist[a][b],c);
	}
	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				uin(dist[i][j],dist[i][k]+dist[k][j]);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			for (int k = 1; k <= K; k++) if (~buy[i][k] && ~sell[j][k]){
				go[i][j] = max(go[i][j],sell[j][k]-buy[i][k]);
			}
		}
	}
	auto check = [&] (int mid) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				d[i][j] = go[i][j] - dist[i][j] * mid;
			}
		}
		for (int k = 1; k <= n; k++)
			for (int i = 1; i <= n; i++)
				for (int j = 1; j <= n; j++)
					d[i][j] = max(d[i][j],d[i][k]+d[k][j]);
		for (int start = 1; start <= n; start++) {
			for (int lst = 1; lst <= n; lst++) if (lst != start && d[start][lst] + go[lst][start] - dist[lst][start] * mid >= 0) return 1;
		}
		return 0;
	};
	int low = 1, high = 1e9, mid, ans = 0;
	while (low <= high) {
		mid = (low+high)/2;
		if (check(mid)) low = (ans = mid) + 1;
		else high = mid - 1;
	}
	printf ("%d\n",ans);
	return 0;
}

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:22:8: 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:25:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf ("%lld %lld",&buy[i][j],&sell[i][j]);
    ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:32:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a,b,c; scanf ("%d %d %d",&a,&b,&c);
              ~~~~~~^~~~~~~~~~~~~~~~~~~~~

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