Submission #474514

#	Time	Username	Problem	Language	Result	Execution time	Memory
474514		Foxyy	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	105 ms	4164 KiB

merchant

#define OPTIMIZE 0
#define Interactive 0
 
#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 100;
const int INF = 0x3f3f3f3f; // INF = 0x3f3f3f3f, INT_MAX
const long long MOD = 1e9+7; // MOD = 1e9+7, 1e8+7, 998244353
const long long LINF = 1e18;
#define INIT(arr, val) fill(arr, arr+(int)(sizeof(arr)/sizeof(arr[0])), val)
#define REP(i, lb, rb, inc) for(int i = (lb); i < (rb); i += inc)
#define RREP(i, rb, lb, dec) for(int i = (rb)-1; i >= (lb); i -= dec)
#define REPN(i, s, n) for(int i = s; i < n; ++i)
#define RREPN(i, n, s) for(int i = n-1; i >= s; --i)
typedef long long ll;
typedef std::vector<int> VI;
typedef std::vector<ll> VLL;
typedef std::vector<string> VSTR;
#define pb push_back
typedef std::pair<int, int> PII;
typedef std::pair<double, double> PDD;
typedef std::pair<ll, ll> PLL;
#define ALL(x) x.begin(), x.end()
#define RALL(x) x.rbegin(), x.rend()
#define SZ(x) ((int)(x).size())
#define endl '\n'
#if !Interactive
#	define Foxyy cin.tie(0); cout.sync_with_stdio(0); cout.tie(0);
#else
#	define Foxyy ;
#endif
#define I_Suck_At_Coding signed main()
 
#if IDE
#	pragma GCC optimize ("trapv")
#endif
 
#if OPTIMIZE
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("sse,sse2,sse3,avx,avx2")
#endif
 
class dummy_ostream : public std::ostream {
	public:
		dummy_ostream():
			std::ostream(&m_sb) {}
	private:
		class NullBuffer : public std::streambuf {
			public:
				int overflow(int c) { return c; }
		} m_sb;
};
class redirect_ostream {
	public:
		redirect_ostream(ostream &_os):
			os(_os) {}
		
		template<class T>
		redirect_ostream& operator << (const T &x) {
			os << x;
			return *this;
		}
	private:
		ostream &os;
};
class dual_ostream {
	public:
		dual_ostream(ostream &_os1, ostream &_os2):
			os1(_os1), os2(_os2) {}
		
		template<class T>
		dual_ostream& operator << (const T &x) {
			os1 << x;
			os2 << x;
			return *this;
		}
	private:
		ostream &os1, &os2;
};
 
#if IDE && !Interactive
#	define Input fin
	ifstream fin("cin.in");
	ofstream fout("cout.out");
	ofstream ferr("cerr.out");
	dual_ostream Output(fout, cout);
	dual_ostream Error(ferr, cerr);
#else
#	define Input cin
		redirect_ostream Output(cout);
#	if IDE
		redirect_ostream Error(cerr);
#	else
		dummy_ostream Error;
#	endif
#endif
 
#define READ(a, t) t a; Input >> a
#define READARR(arr, n) REP(___i, 0, (n), 1) Input >> arr[___i];
#define PRINTARR(s, arr, n) { REP(___i, 0, (n), 1) s << arr[___i] << " "; s << endl; }
#define RI(a) READ(a, int)
#define RD(a) READ(a, double)
#define RC(a) READ(a, char)
#define RLL(a) READ(a, ll)
#define RSTR(a) READ(a, string)
#define RVI(__a, n) VI __a(n); READARR(__a, n)
#define RVLL(__a, n) VLL __a(n); READARR(__a, n)
#define RVSTR(__a, n) VSTR __a(n); READARR(__a, n)
 
#define randInt(l, r) uniform_int_distribution<int>(l, r-1)(rng)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

ll g[MAXN][MAXN];
ll g2[MAXN][MAXN];
ll profit[MAXN][MAXN];
ll B[MAXN][1000], S[MAXN][1000];
int N, M, K;

void floyd_warshall(ll g[MAXN][MAXN]) {
	REPN(k, 0, N) REPN(i, 0, N) REPN(j, 0, N)
		g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
}

void init() {
	fill(g[0], g[MAXN-1]+MAXN, LINF);
	Input >> N >> M >> K;
	REPN(i, 0, N)
		REPN(k, 0, K)
			Input >> B[i][k] >> S[i][k];
	REPN(i, 0, M) {
		RI(a); RI(b); RI(c);
		g[a-1][b-1] = c;
	}
	floyd_warshall(g);
	REPN(i, 0, N) REPN(j, 0, N) REPN(k, 0, K)
		if (B[i][k] != -1 and S[j][k] != -1)
			profit[i][j] = max(profit[i][j], S[j][k] - B[i][k]);
}

bool check(ll m) {
	REPN(i, 0, N) REPN(j, 0, N)
		g2[i][j] = m * min(g[i][j], LINF/m) - profit[i][j];
	floyd_warshall(g2);
	REPN(i, 0, N) if (g2[i][i] <= 0) return true;
	return false;
}

void solve() {
	ll l = 0, r = INF;
	while(l < r-1) {
		ll mid = l+r >> 1;
		if (check(mid)) l = mid;
		else			r = mid;
	}
	Output << l << endl;
}

I_Suck_At_Coding {
	Foxyy
	
	int T = 1;
//	Input >> T;
	while(T--) {
		init();
		solve();
	}
}

Compilation message (stderr)

merchant.cpp: In function 'void solve()':
merchant.cpp:152:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  152 |   ll mid = l+r >> 1;
      |            ~^~

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