Submission #540834

#	Time	Username	Problem	Language	Result	Execution time	Memory
540834		LucaDantas	Travelling Merchant (APIO17_merchant)	C++17	0 / 100	1081 ms	1236 KiB

merchant

#pragma GCC optmize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;

constexpr int maxn = 51, maxk = 1010, max_caminho = 2510, inf = 0x3f3f3f3f;

int valor[maxn][maxn]; // grafo completo final
int dist[maxn][maxn]; // floyd warshall

int b[maxn][maxk], s[maxn][maxk];

int dp[max_caminho][maxn]; // maior valor pra chegar nesse vértice com esse tempo

int main() {
	int n, m, k; scanf("%d %d %d", &n, &m, &k);
	memset(dist, 0x3f, sizeof dist);
	
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= k; j++)
			scanf("%d %d", &b[i][j], &s[i][j]);
	
	for(int i = 0; i < m; i++) {
		int a, b, w; scanf("%d %d %d", &a, &b, &w);
		dist[a][b] = w;
	}

	for(int l = 1; l <= n; l++)
		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= n; j++)
				if(dist[i][l] < inf && dist[l][j] < inf)
					dist[i][j] = min(dist[i][j], dist[i][l] + dist[l][j]);

	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			for(int l = 1; l <= k; l++)
				if(b[i][l] != -1 && s[j][l] != -1)
					valor[i][j] = max(valor[i][j], -b[i][l] +s[j][l]); // compro 'l' em 'i' e vendo em 'j'

	/* for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			printf("%d %d %d\n", i, j, valor[i][j]); */

	int ans = 0;
	for(int st = 1; st <= n; st++) {
		for(int tempo = 0; tempo < max_caminho; tempo++)
			for(int i = 1; i <= n; i++)
				dp[tempo][i] = -inf;
		
		dp[0][st] = 0;

		for(int tempo = 0; tempo < max_caminho; tempo++) {
			for(int i = 1; i <= n; i++) {
				if(dp[tempo][i] == -inf) continue;
				for(int j = 1; j <= n; j++) if(tempo + dist[i][j] < max_caminho)
					dp[ tempo + dist[i][j] ][j] = max(dp[tempo + dist[i][j]][j], dp[tempo][i] + valor[i][j]);
			}
		}

		for(int tempo = 1; tempo < max_caminho; tempo++)
			ans = max(ans, dp[tempo][st] / tempo);
	}

	printf("%d\n", ans);
}

Compilation message (stderr)

merchant.cpp:1: warning: ignoring '#pragma GCC optmize' [-Wunknown-pragmas]
    1 | #pragma GCC optmize("O3")
      | 
merchant.cpp: In function 'int main()':
merchant.cpp:16:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |  int n, m, k; scanf("%d %d %d", &n, &m, &k);
      |               ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:21:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |    scanf("%d %d", &b[i][j], &s[i][j]);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:24:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |   int a, b, w; scanf("%d %d %d", &a, &b, &w);
      |                ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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