Submission #376461

#	Time	Username	Problem	Language	Result	Execution time	Memory
376461		AriaH	Travelling Merchant (APIO17_merchant)	C++11	100 / 100	109 ms	5128 KiB

merchant

/** I can do this all day **/

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;

typedef long long                   ll;
typedef long double                 ld;
typedef pair<int,int>               pii;
typedef pair<ll,ll>                 pll;
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define Mp                          make_pair
#define SZ(x)			    		(int)x.size()
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io                     freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);

const int N = 1e2 + 10;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll inf = 2e9;
const int LOG = 22;
const int N2 = 10000;

ll pw(ll a , ll b, ll M)  { return (!b ? 1 : (b & 1 ? (a * pw(a * a % M, b / 2, M)) % M : pw(a * a % M, b / 2, M))); }

int n, m, K;

ll dis[N][N], D[N][N], Mx[N][N], B[N][N2], S[N][N2];

void calc(int v, int u)
{
	Mx[v][u] = 0;
	for(int i = 1; i <= K; i ++)
	{
		if(S[u][i] == -1 || B[v][i] == -1) continue;
		Mx[v][u] = max(Mx[v][u], S[u][i] - B[v][i]);
	}
}

bool check(ll x)
{
	// printf("checking D\n");
	for(int i = 1; i <= n; i ++)
	{
		for(int j = 1; j <= n; j ++)
		{
			if(dis[i][j] >= inf) D[i][j] = -inf;
			else D[i][j] = Mx[i][j] - dis[i][j] * x;
			///printf("%lld ", D[i][j]);
		}
		D[i][i] = -inf;
		///printf("\n");
	}
	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 i = 1; i <= n; i ++)
	{
		if(D[i][i] >= 0) return 1;
	}
	return 0;
}

int main()
{
	scanf("%d%d%d", &n, &m, &K);
	for(int i = 1; i <= n; i ++)
	{
		for(int j = 1; j <= K; j ++)
		{
			scanf("%lld%lld", &B[i][j], &S[i][j]);
		}
	}
	for(int i = 1; i <= n; i ++) for(int j = 1; j <= n; j ++) calc(i, j), dis[i][j] = inf;
	for(int i = 1; i <= m; i ++)
	{
		ll a, b, c;
		scanf("%lld%lld%lld", &a, &b, &c);
		dis[a][b] = min(dis[a][b], c);
	}
	for(int k = 1; k <= n; k ++)
	{
		for(int i = 1; i <= n; i ++)
		{
			for(int j = 1; j <= n; j ++)
			{
				dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
			}
		}
	}
	/*printf("checking Mx\n");
	for(int i = 1; i <= n; i ++)
	{
		for(int j = 1; j <= n; j ++)
		{
			printf("%lld ", Mx[i][j]);
		}
		printf("\n");
	} */
	ll d = 0, up = inf;
	while(up - d > 1)
	{
		ll mid = (up + d) >> 1;
		if(check(mid)) d = mid;
		else up = mid;
	}
	printf("%lld", d);
    return 0;
}

/** test corner cases(n = 1?) watch for overflow or minus indices **/

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:75:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   75 |  scanf("%d%d%d", &n, &m, &K);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:80:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   80 |    scanf("%lld%lld", &B[i][j], &S[i][j]);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:87:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   87 |   scanf("%lld%lld%lld", &a, &b, &c);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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