제출 #945501

#제출 시각아이디문제언어결과실행 시간메모리
945501Wael여행하는 상인 (APIO17_merchant)C++17
100 / 100
78 ms1504 KiB
#include <bits/stdc++.h> using namespace std; #define log(x) (63^__builtin_clzll(x)) #define endl '\n' #define all(x) (x).begin() , (x).end() const int mod = 1e9 + 7, lg = 22 , N = 1e6 + 1; void solve() { int n, m, k; cin >> n >> m >> k; vector<vector<int>> b(n, vector<int>(k)), s(n, vector<int>(k)); for(int i = 0; i < n; ++i) for(int item = 0; item < k; ++item) cin >> b[i][item] >> s[i][item]; vector<vector<int>> dis(n, vector<int>(n, 1e9)), maxGain(n, vector<int>(n, 0)); for(int i = 0; i < m; ++i) { int u, v, len; cin >> u >> v >> len; --u, --v; dis[u][v] = min(dis[u][v], len); } for(int mid = 0; mid < n; ++mid) for(int start = 0; start < n; ++start) for(int end = 0; end < n; ++end) dis[start][end] = min(dis[start][end], dis[start][mid] + dis[mid][end]); for(int i = 0; i < n; ++i) { for(int j = 0; j < n; ++j) { if(dis[i][j] == 1e9) continue; for(int item = 0; item < k; ++item) if(s[j][item] != -1 && b[i][item] != -1) maxGain[i][j] = max(maxGain[i][j], s[j][item] - b[i][item]); } } int l = 0, r = 1e9; while(l <= r) { int mid = (l + r) / 2; vector<vector<long long>> dp(n, vector<long long>(n, -1e18)); for(int i = 0; i < n; ++i) { for(int j = 0; j < n; ++j) { if(dis[i][j] == 1e9) continue; dp[i][j] = max(dp[i][j], (long long)maxGain[i][j] - (long long)dis[i][j] * mid); } } for(int mid = 0; mid < n; ++mid) for(int start = 0; start < n; ++start) for(int end = 0; end < n; ++end) dp[start][end] = max(dp[start][end], dp[start][mid] + dp[mid][end]); int ok = 0; for(int i = 0; i < n; ++i) { if(dp[i][i] >= 0) ok = 1; } if(ok) l = mid + 1; else r = mid - 1; } cout << max(0, l - 1) << endl; return; } main() { ios_base::sync_with_stdio(false);cout.tie(nullptr);cin.tie(nullptr); int t; //cin >> t; t = 1; while(t--) solve(); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

merchant.cpp:69:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   69 | main() {
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...