제출 #474513

#제출 시각아이디문제언어결과실행 시간메모리
474513Foxyy여행하는 상인 (APIO17_merchant)C++17
33 / 100
97 ms2892 KiB
#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()); int g[MAXN][MAXN]; int g2[MAXN][MAXN]; int profit[MAXN][MAXN]; int B[MAXN][1000], S[MAXN][1000]; int N, M, K; void floyd_warshall(int 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, INF); 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], INF/(int)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(); } }

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

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