oj.uz

답안 #669341

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
669341 2022-12-06T09:24:29 Z LittlePants 여행하는 상인 (APIO17_merchant) C++17
100 / 100
 90 ms 4208 KB 
#include<bits/stdc++.h>
#define loli
using namespace std;
typedef long long ll;
#define int ll
#define pii pair<int, int>
#define X first
#define Y second
#define SZ(a) ((int)a.size())
#define ALL(v) v.begin(), v.end()
#define pb push_back
#define eb emplace_back
#define push emplace
#define lb(x, v) lower_bound(ALL(x), v)
#define ub(x, v) upper_bound(ALL(x), v)
#define re(x) reverse(ALL(x))
#define uni(x) x.resize(unique(ALL(x)) - x.begin())
#define inf 1000000000
#define INF 1000000000000000000
#define mod 1000000007
#define get_bit(x, y) ((x>>y)&1)
#define mkp make_pair
#define IO ios_base::sync_with_stdio(0); cin.tie(0);
void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
    cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
    for (; l != r; ++l) cout << *l << " \n"[l + 1 == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
    return o >> a.X >> a.Y;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
    return o << '(' << a.X << ", " << a.Y << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
    bool is = false;
    if (a.empty()) return o << "{}";
    for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
    return o << '}';
}
#ifdef loli
#define test(args...) abc("[" + string(#args) + "]", args)
#else
#define test(args...) void(0)
#endif
const int mxN = 100 + 5, mxK = 1000 + 5;

int n, m, k, b[mxN][mxK], s[mxN][mxK];

int dp[mxN][mxK];
int profit[mxN][mxN];
int mat[mxN][mxN], tmp[mxN][mxN];

int check(int thres) {
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) { 
        if (mat[i][j] != INF) tmp[i][j] = profit[i][j] - mat[i][j] * thres;
        else tmp[i][j] = -INF;
    }
    
    for (int x = 1; x <= n; x++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) {
        tmp[i][j] = max(tmp[i][j], tmp[i][x] + tmp[x][j]);
    }

    int ans = -INF;
    for (int i = 1; i <= n; i++) ans = max(ans, tmp[i][i]);
//    test(thres, ans);
    return ans >= 0;
}

inline void solve() {
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            cin >> b[i][j] >> s[i][j]; 
        }
    }

    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) for (int c = 1; c <= k; c++) {
        if (b[i][c] != -1 and s[j][c] != -1) 
            profit[i][j] = max(profit[i][j], s[j][c] - b[i][c]);
    }

   for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) mat[i][j] = INF;
   for (int i = 0; i < m; i++) {
       int u, v, t; 
       cin >> u >> v >> t;
       mat[u][v] = t;
   }

   for (int x = 1; x <= n; x++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) mat[i][j] = min(mat[i][j], mat[i][x] + mat[x][j]);

    // binary search
    int l = 0, r = 1e9 + 1;
    while (l < r) {
        int mid = (l + r + 1) >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    cout << l << '\n';
}

signed main() {
	IO;	
	solve();	
}

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 72 ms 2060 KB Output is correct
2 Correct 41 ms 1284 KB Output is correct
3 Correct 31 ms 1236 KB Output is correct
4 Correct 5 ms 724 KB Output is correct
5 Correct 5 ms 712 KB Output is correct
6 Correct 5 ms 724 KB Output is correct
7 Correct 5 ms 852 KB Output is correct
8 Correct 1 ms 328 KB Output is correct
9 Correct 5 ms 724 KB Output is correct
10 Correct 5 ms 724 KB Output is correct
11 Correct 4 ms 712 KB Output is correct
12 Correct 1 ms 328 KB Output is correct
13 Correct 6 ms 868 KB Output is correct

Subtask #2
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 724 KB Output is correct
2 Correct 5 ms 852 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 5 ms 724 KB Output is correct
5 Correct 5 ms 724 KB Output is correct
6 Correct 4 ms 712 KB Output is correct
7 Correct 1 ms 328 KB Output is correct
8 Correct 6 ms 868 KB Output is correct
9 Correct 6 ms 852 KB Output is correct
10 Correct 6 ms 852 KB Output is correct
11 Correct 6 ms 848 KB Output is correct
12 Correct 5 ms 768 KB Output is correct
13 Correct 6 ms 848 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 5 ms 844 KB Output is correct
16 Correct 5 ms 912 KB Output is correct
17 Correct 5 ms 852 KB Output is correct
18 Correct 7 ms 852 KB Output is correct
19 Correct 7 ms 944 KB Output is correct
20 Correct 7 ms 852 KB Output is correct
21 Correct 5 ms 852 KB Output is correct
22 Correct 5 ms 852 KB Output is correct
23 Correct 6 ms 872 KB Output is correct
24 Correct 5 ms 836 KB Output is correct
25 Correct 5 ms 852 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 5 ms 852 KB Output is correct
28 Correct 5 ms 852 KB Output is correct
29 Correct 6 ms 852 KB Output is correct
30 Correct 7 ms 868 KB Output is correct
31 Correct 5 ms 852 KB Output is correct

Subtask #3
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 852 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 5 ms 852 KB Output is correct
4 Correct 5 ms 852 KB Output is correct
5 Correct 6 ms 852 KB Output is correct
6 Correct 7 ms 868 KB Output is correct
7 Correct 5 ms 852 KB Output is correct
8 Correct 47 ms 1492 KB Output is correct
9 Correct 84 ms 2144 KB Output is correct
10 Correct 33 ms 1364 KB Output is correct
11 Correct 37 ms 1492 KB Output is correct
12 Correct 42 ms 1492 KB Output is correct
13 Correct 34 ms 1428 KB Output is correct

Subtask #4
34.0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 852 KB Output is correct
2 Correct 6 ms 852 KB Output is correct
3 Correct 6 ms 848 KB Output is correct
4 Correct 5 ms 768 KB Output is correct
5 Correct 6 ms 848 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 5 ms 844 KB Output is correct
8 Correct 5 ms 912 KB Output is correct
9 Correct 5 ms 852 KB Output is correct
10 Correct 7 ms 852 KB Output is correct
11 Correct 7 ms 944 KB Output is correct
12 Correct 7 ms 852 KB Output is correct
13 Correct 5 ms 852 KB Output is correct
14 Correct 5 ms 852 KB Output is correct
15 Correct 6 ms 872 KB Output is correct
16 Correct 5 ms 836 KB Output is correct
17 Correct 47 ms 1492 KB Output is correct
18 Correct 84 ms 2144 KB Output is correct
19 Correct 33 ms 1364 KB Output is correct
20 Correct 37 ms 1492 KB Output is correct
21 Correct 42 ms 1492 KB Output is correct
22 Correct 34 ms 1428 KB Output is correct
23 Correct 5 ms 852 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 5 ms 852 KB Output is correct
26 Correct 5 ms 852 KB Output is correct
27 Correct 6 ms 852 KB Output is correct
28 Correct 7 ms 868 KB Output is correct
29 Correct 5 ms 852 KB Output is correct
30 Correct 72 ms 2060 KB Output is correct
31 Correct 41 ms 1284 KB Output is correct
32 Correct 31 ms 1236 KB Output is correct
33 Correct 5 ms 724 KB Output is correct
34 Correct 5 ms 712 KB Output is correct
35 Correct 5 ms 724 KB Output is correct
36 Correct 5 ms 852 KB Output is correct
37 Correct 1 ms 328 KB Output is correct
38 Correct 5 ms 724 KB Output is correct
39 Correct 5 ms 724 KB Output is correct
40 Correct 4 ms 712 KB Output is correct
41 Correct 1 ms 328 KB Output is correct
42 Correct 6 ms 868 KB Output is correct
43 Correct 39 ms 1412 KB Output is correct
44 Correct 45 ms 1620 KB Output is correct
45 Correct 54 ms 2548 KB Output is correct
46 Correct 33 ms 1600 KB Output is correct
47 Correct 46 ms 1620 KB Output is correct
48 Correct 39 ms 1620 KB Output is correct
49 Correct 90 ms 4112 KB Output is correct
50 Correct 1 ms 328 KB Output is correct
51 Correct 1 ms 340 KB Output is correct
52 Correct 38 ms 1364 KB Output is correct
53 Correct 32 ms 1364 KB Output is correct
54 Correct 37 ms 1464 KB Output is correct
55 Correct 32 ms 1404 KB Output is correct
56 Correct 32 ms 1328 KB Output is correct
57 Correct 1 ms 340 KB Output is correct
58 Correct 7 ms 1016 KB Output is correct
59 Correct 7 ms 984 KB Output is correct
60 Correct 7 ms 976 KB Output is correct
61 Correct 83 ms 4208 KB Output is correct
62 Correct 83 ms 4180 KB Output is correct
63 Correct 1 ms 340 KB Output is correct