oj.uz

답안 #118988

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
118988 2019-06-20T07:05:44 Z MAMBA 여행하는 상인 (APIO17_merchant) C++17
0 / 100
 108 ms 2296 KB 
#include <bits/stdc++.h>

using namespace std;

inline void fileIO(string s) {
	freopen((s + ".in").c_str(), "r", stdin);
	freopen((s + ".out").c_str(), "w", stdout);
}

inline void read() {}
template <class S>
inline void read(S &arg) {
	cin >> arg;
}
template <class S>
inline void readA(S Lptr, S Rptr) {
	while (Lptr != Rptr) {
		read(*Lptr);
		Lptr++;
	}
}
template <class S, class... T>
inline void read(S &arg, T &... rest) {
	read(arg);
	read(rest...);
}

inline void write() {}
template <class S>
inline void write(S arg) {
	cout << arg;
}
template <class S>
inline void writeA(S Lptr, S Rptr, char del = ' ') {
	if (Lptr != Rptr) {
		write(*Lptr);
		Lptr++;
	}
	while (Lptr != Rptr) {
		write(del);
		write(*Lptr);
		Lptr++;
	}
}
template <class S, class... T>
inline void write(S arg, T... rest) {
	write(arg);
	write(' ');
	write(rest...);
}

#define rep(i, j, k) for (int i = j; i < (int)k; i++)
#define pb push_back
#define mt make_tuple
#define all(x) x.begin(), x.end()

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

template <class T, class S>
inline bool smin(T &a, S b) {
	return (T)b < a ? a = b, 1 : 0;
}
template <class T, class S>
inline bool smax(T &a, S b) {
	return a < (T)b ? a = b, 1 : 0;
}

constexpr int MOD = 1e9 + 7;
constexpr int N = 110;
constexpr int K = 1010;

template <typename T>
inline T mod(T &v) {
	return v = (v % MOD + MOD) % MOD;
}
template <typename S, typename T>
inline S add(S &l, T r) {
	return mod(l += r);
}

ll po(ll v, ll u) {
	return u ? po(v * v % MOD, u >> 1) * (u & 1 ? v : 1) % MOD : 1;
}

int n , m , k;
ll B[N][K];
ll S[N][K];
ll mat[N][N];
ll dist[N][N];
ll d[N][N];


int32_t main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	memset(dist, 63 , sizeof(dist));
	read(n , m, k);

	rep(i , 0 , n) {
		dist[i][i] = 0;
		readA(B[i] , B[i] + k);
		readA(S[i] , S[i] + k);
	}

	rep(i , 0 , m) {
		int u , v , w;
		read(u , v , w);
		u--, v--;
		smin(dist[u][v] , w);
	}

	rep(z , 0 , n) 
		rep(i , 0 , n)
		rep(j , 0 , n)
		smin(dist[i][j] , dist[i][z] + dist[z][j]);

	rep(i , 0 , n) {
		rep(j , 0 , n)
			rep(z , 0 , k)
			if (~B[i][z] && ~S[j][z])
				smax(mat[i][j] , S[j][z] - B[i][z]);
	}


	auto f = [](int limit) -> bool {

		memset(d , 63 , sizeof(d));

		rep(i , 0 , n)
			rep(j , 0 , n)
			if (dist[i][j] != dist[N - 1][N - 1]) 
				d[i][j] = dist[i][j] * limit - mat[i][j];


		rep(z , 0 , n)
			rep(i , 0 , n)
			rep(j , 0 , n)
          		if (max(d[i][z] , d[z][j]) != d[N - 1][N - 1])
				smin(d[i][j] , d[i][z] + d[z][j]);

		rep(i , 0 , n)
			rep(j , i + 1, n)
			if (d[i][j] + d[j][i] <= 0)
				return true;
		return false;
	};


	int lo = 0, hi = 2e9 + 10;
	while (lo != hi - 1) {
		int mid = lo + hi >> 1;
		if (f(mid))
			lo = mid;
		else
			hi = mid;
	}
	write(lo);

	return 0;
}

Compilation message

merchant.cpp: In function 'int32_t main()':
merchant.cpp:155:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = lo + hi >> 1;
             ~~~^~~~

Subtask #1
0 / 12.0

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

Subtask #2
0 / 21.0

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

Subtask #3
0 / 33.0

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

Subtask #4
0 / 34.0

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