제출 #265348

#제출 시각아이디문제언어결과실행 시간메모리
265348abacaba여행하는 상인 (APIO17_merchant)C++14
컴파일 에러
0 ms0 KiB
#include <iostream> #include <string> #include <unordered_map> #include <unordered_set> #include <cstring> #include <chrono> #include <vector> #include <map> #include <random> #include <set> #include <algorithm> #include <math.h> #include <cstdio> #include <stdio.h> #include <queue> #include <bitset> #include <cstdlib> #include <deque> #include <cassert> #include <stack> #include <bits/stdc++.h> using namespace std; // #include <ext/pb_ds/assoc_container.hpp> // #include <ext/pb_ds/tree_policy.hpp> // using namespace __gnu_pbds; // typedef tree <int, null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; #define mp make_pair #define f first #define se second #define pb push_back #define ppb pop_back #define emb emplace_back #define ll long long #define ull unsigned long long #define cntbit(x) __builtin_popcount(x) #define endl '\n' #define uset unordered_set #define umap unordered_map #define pii pair<int, int> #define ld long double #define pll pair<long long, long long> mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); template <typename T> inline T range(T l, T r) { return uniform_int_distribution<T>(l, r)(rng); } template <typename T> void Min(T &a, T b) { a = min(a, b); } template <typename T> void Max(T &a, T b) { a = max(a, b); } #define int long long const int mod = 1e9 + 7; const int inf = 2e15; const int N = 1e2 + 15; const int K = 1e3 + 15; int n, m, k, buy[N][K], sell[N][K]; int g[N][N]; int mx[N][N], d[N][N]; int dp[N][N]; bool used[N]; int rec(int x, int y) { if(dp[x][y] != inf) return dp[x][y]; dp[x][y] = mx[x][y]; for(int k = 1; k <= n; ++k) if(k != x && k != y) { Min(dp[x][y], rec(x, k) + rec(k, y)); Max(dp[x][y], -inf); } return dp[x][y]; } bool check(int mid) { for(int i = 0; i < N; ++i) { fill(d[i], d[i] + N, inf); fill(dp[i], dp[i] + N, inf); } for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j) if(g[i][j]) d[i][j] = g[i][j] * mid; for(int k = 1; k <= n; ++k) for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j) Min(d[i][j], d[i][k] + d[k][j]); memcpy(mx, d, sizeof(d)); for(int i = 1; i <= n; ++i) dp[i][i] = 0; for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j) for(int s = 1; s <= k; ++s) if(buy[i][s] != -1 && sell[j][s] != -1) { Min(mx[i][j], d[i][j] + buy[i][s] - sell[j][s]); Max(mx[i][j], -inf); } int ans = inf; for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j) if(i != j) Min(ans, rec(i, j) + mx[j][i]); return ans <= 0; } main() { ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0); // freopen("input.txt", "r", stdin); cin >> n >> m >> k; for(int i = 1; i <= n; ++i) for(int j = 1; j <= k; ++j) cin >> buy[i][j] >> sell[i][j]; for(int i = 1; i <= m; ++i) { int u, v; cin >> u >> v; cin >> g[u][v]; } int l = 1, r = 2e9, res = 0; while(l <= r) { int mid = (l + r) / 2; if(check(mid)) l = mid + 1, res = mid; else r = mid - 1; } cout << res << endl; return 0; }#include <iostream> #include <string> #include <unordered_map> #include <unordered_set> #include <cstring> #include <chrono> #include <vector> #include <map> #include <random> #include <set> #include <algorithm> #include <math.h> #include <cstdio> #include <stdio.h> #include <queue> #include <bitset> #include <cstdlib> #include <deque> #include <cassert> #include <stack> #include <bits/stdc++.h> using namespace std; // #include <ext/pb_ds/assoc_container.hpp> // #include <ext/pb_ds/tree_policy.hpp> // using namespace __gnu_pbds; // typedef tree <int, null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; #define mp make_pair #define f first #define se second #define pb push_back #define ppb pop_back #define emb emplace_back #define ll long long #define ull unsigned long long #define cntbit(x) __builtin_popcount(x) #define endl '\n' #define uset unordered_set #define umap unordered_map #define pii pair<int, int> #define ld long double #define pll pair<long long, long long> mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); template <typename T> inline T range(T l, T r) { return uniform_int_distribution<T>(l, r)(rng); } template <typename T> void Min(T &a, T b) { a = min(a, b); } template <typename T> void Max(T &a, T b) { a = max(a, b); } #define int long long const int mod = 1e9 + 7; const int inf = 2e15; const int N = 1e2 + 15; const int K = 1e3 + 15; int n, m, k, buy[N][K], sell[N][K]; int g[N][N]; int mx[N][N], d[N][N]; int dp[N][N]; bool used[N]; int rec(int x, int y) { if(dp[x][y] != inf) return dp[x][y]; dp[x][y] = mx[x][y]; for(int k = 1; k <= n; ++k) if(k != x && k != y) { Min(dp[x][y], rec(x, k) + rec(k, y)); Max(dp[x][y], -inf); } return dp[x][y]; } bool check(int mid) { for(int i = 0; i < N; ++i) { fill(d[i], d[i] + N, inf); fill(dp[i], dp[i] + N, inf); } for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j) if(g[i][j]) d[i][j] = g[i][j] * mid; for(int k = 1; k <= n; ++k) for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j) Min(d[i][j], d[i][k] + d[k][j]); memcpy(mx, d, sizeof(d)); for(int i = 1; i <= n; ++i) dp[i][i] = 0; for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j) for(int s = 1; s <= k; ++s) if(buy[i][s] != -1 && sell[j][s] != -1) { Min(mx[i][j], d[i][j] + buy[i][s] - sell[j][s]); Max(mx[i][j], -inf); } int ans = inf; for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j) if(i != j) Min(ans, rec(i, j) + mx[j][i]); return ans <= 0; } main() { ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0); // freopen("input.txt", "r", stdin); cin >> n >> m >> k; for(int i = 1; i <= n; ++i) for(int j = 1; j <= k; ++j) cin >> buy[i][j] >> sell[i][j]; for(int i = 1; i <= m; ++i) { int u, v; cin >> u >> v; cin >> g[u][v]; } int l = 1, r = 2e9, res = 0; while(l <= r) { int mid = (l + r) / 2; if(check(mid)) l = mid + 1, res = mid; else r = mid - 1; } cout << res << endl; return 0; }

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

merchant.cpp:142:2: error: stray '#' in program
  142 | }#include <iostream>
      |  ^
merchant.cpp:120:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  120 | main() {
      |      ^
merchant.cpp:142:3: error: 'include' does not name a type
  142 | }#include <iostream>
      |   ^~~~~~~
merchant.cpp:186:9: error: redefinition of 'std::mt19937 rng'
  186 | mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
      |         ^~~
merchant.cpp:45:9: note: 'std::mt19937 rng' previously declared here
   45 | mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
      |         ^~~
merchant.cpp:188:32: error: redefinition of 'template<class T> T range(T, T)'
  188 | template <typename T> inline T range(T l, T r) {
      |                                ^~~~~
merchant.cpp:47:32: note: 'template<class T> T range(T, T)' previously declared here
   47 | template <typename T> inline T range(T l, T r) {
      |                                ^~~~~
merchant.cpp:192:28: error: redefinition of 'template<class T> void Min(T&, T)'
  192 | template <typename T> void Min(T &a, T b) {
      |                            ^~~
merchant.cpp:51:28: note: 'template<class T> void Min(T&, T)' previously declared here
   51 | template <typename T> void Min(T &a, T b) {
      |                            ^~~
merchant.cpp:196:28: error: redefinition of 'template<class T> void Max(T&, T)'
  196 | template <typename T> void Max(T &a, T b) {
      |                            ^~~
merchant.cpp:55:28: note: 'template<class T> void Max(T&, T)' previously declared here
   55 | template <typename T> void Max(T &a, T b) {
      |                            ^~~
merchant.cpp:202:11: error: redefinition of 'const long long int mod'
  202 | const int mod = 1e9 + 7;
      |           ^~~
merchant.cpp:61:11: note: 'const long long int mod' previously defined here
   61 | const int mod = 1e9 + 7;
      |           ^~~
merchant.cpp:203:11: error: redefinition of 'const long long int inf'
  203 | const int inf = 2e15;
      |           ^~~
merchant.cpp:62:11: note: 'const long long int inf' previously defined here
   62 | const int inf = 2e15;
      |           ^~~
merchant.cpp:204:11: error: redefinition of 'const long long int N'
  204 | const int N = 1e2 + 15;
      |           ^
merchant.cpp:63:11: note: 'const long long int N' previously defined here
   63 | const int N = 1e2 + 15;
      |           ^
merchant.cpp:205:11: error: redefinition of 'const long long int K'
  205 | const int K = 1e3 + 15;
      |           ^
merchant.cpp:64:11: note: 'const long long int K' previously defined here
   64 | const int K = 1e3 + 15;
      |           ^
merchant.cpp:206:5: error: redefinition of 'long long int n'
  206 | int n, m, k, buy[N][K], sell[N][K];
      |     ^
merchant.cpp:65:5: note: 'long long int n' previously declared here
   65 | int n, m, k, buy[N][K], sell[N][K];
      |     ^
merchant.cpp:206:8: error: redefinition of 'long long int m'
  206 | int n, m, k, buy[N][K], sell[N][K];
      |        ^
merchant.cpp:65:8: note: 'long long int m' previously declared here
   65 | int n, m, k, buy[N][K], sell[N][K];
      |        ^
merchant.cpp:206:11: error: redefinition of 'long long int k'
  206 | int n, m, k, buy[N][K], sell[N][K];
      |           ^
merchant.cpp:65:11: note: 'long long int k' previously declared here
   65 | int n, m, k, buy[N][K], sell[N][K];
      |           ^
merchant.cpp:206:14: error: redefinition of 'long long int buy [115][1015]'
  206 | int n, m, k, buy[N][K], sell[N][K];
      |              ^~~
merchant.cpp:65:14: note: 'long long int buy [115][1015]' previously declared here
   65 | int n, m, k, buy[N][K], sell[N][K];
      |              ^~~
merchant.cpp:206:25: error: redefinition of 'long long int sell [115][1015]'
  206 | int n, m, k, buy[N][K], sell[N][K];
      |                         ^~~~
merchant.cpp:65:25: note: 'long long int sell [115][1015]' previously declared here
   65 | int n, m, k, buy[N][K], sell[N][K];
      |                         ^~~~
merchant.cpp:207:5: error: redefinition of 'long long int g [115][115]'
  207 | int g[N][N];
      |     ^
merchant.cpp:66:5: note: 'long long int g [115][115]' previously declared here
   66 | int g[N][N];
      |     ^
merchant.cpp:209:5: error: redefinition of 'long long int mx [115][115]'
  209 | int mx[N][N], d[N][N];
      |     ^~
merchant.cpp:68:5: note: 'long long int mx [115][115]' previously declared here
   68 | int mx[N][N], d[N][N];
      |     ^~
merchant.cpp:209:15: error: redefinition of 'long long int d [115][115]'
  209 | int mx[N][N], d[N][N];
      |               ^
merchant.cpp:68:15: note: 'long long int d [115][115]' previously declared here
   68 | int mx[N][N], d[N][N];
      |               ^
merchant.cpp:210:5: error: redefinition of 'long long int dp [115][115]'
  210 | int dp[N][N];
      |     ^~
merchant.cpp:69:5: note: 'long long int dp [115][115]' previously declared here
   69 | int dp[N][N];
      |     ^~
merchant.cpp:212:6: error: redefinition of 'bool used [115]'
  212 | bool used[N];
      |      ^~~~
merchant.cpp:71:6: note: 'bool used [115]' previously declared here
   71 | bool used[N];
      |      ^~~~
merchant.cpp:214:5: error: redefinition of 'long long int rec(long long int, long long int)'
  214 | int rec(int x, int y) {
      |     ^~~
merchant.cpp:73:5: note: 'long long int rec(long long int, long long int)' previously defined here
   73 | int rec(int x, int y) {
      |     ^~~
merchant.cpp:226:6: error: redefinition of 'bool check(long long int)'
  226 | bool check(int mid) {
      |      ^~~~~
merchant.cpp:85:6: note: 'bool check(long long int)' previously defined here
   85 | bool check(int mid) {
      |      ^~~~~
merchant.cpp:261:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  261 | main() {
      |      ^
merchant.cpp:261:1: error: redefinition of 'int main()'
  261 | main() {
      | ^~~~
merchant.cpp:120:1: note: 'int main()' previously defined here
  120 | main() {
      | ^~~~