제출 #725839

#제출 시각아이디문제언어결과실행 시간메모리
725839quiet_space여행하는 상인 (APIO17_merchant)C++14
100 / 100
63 ms3400 KiB
#include <bits/stdc++.h> #define FOR(i,j,k) for(int i=j; i<=k; ++i) #define ROF(i,j,k) for(int i=j; i>=k; --i) inline int read (void) { int x = 0, f = 1, ch = getchar(); while(!isdigit(ch)) { if(ch == '-') f = -f; ch = getchar(); } while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } using ll = long long; const int maxn = 105; const int maxk = 1005; int b[maxn][maxk], s[maxn][maxk], e[maxn][maxn]; ll d[maxn][maxn], f[maxn][maxn]; int main (void) { int n = read(), m = read(), k = read(); FOR(i,1,n) FOR(j,1,k) { b[i][j] = read(), s[i][j] = read(); if(b[i][j] == -1) b[i][j] = 1 << 30; if(s[i][j] == -1) s[i][j] = 0; } FOR(i,1,n) FOR(j,1,n) FOR(t,1,k) e[i][j] = std::max(e[i][j], s[j][t] - b[i][t]); FOR(i,1,n) FOR(j,1,n) d[i][j] = 1 << 30; FOR(i,1,m) { int x = read(), y = read(), c = read(); d[x][y] = c; } FOR(i,1,n) d[i][i] = 0; FOR(t,1,n) FOR(i,1,n) FOR(j,1,n) d[i][j] = std::min(d[i][j], d[i][t] + d[t][j]); int left = 1, right = 1e9, mid, ans = 0; while(left <= right) { mid = (left + right >> 1); FOR(i,1,n) FOR(j,1,n) f[i][j] = i == j ? -1ll << 60 : e[i][j] - 1ll * mid * d[i][j]; FOR(t,1,n) FOR(i,1,n) FOR(j,1,n) f[i][j] = std::max(f[i][j], f[i][t] + f[t][j]); bool flag = 0; FOR(i,1,n) if(f[i][i] >= 0) { flag = 1; break; } if(flag) ans = mid, left = mid + 1; else right = mid - 1; } printf("%d\n", ans); return 0; }

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

merchant.cpp: In function 'int main()':
merchant.cpp:33:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |     mid = (left + right >> 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...