oj.uz

답안 #57308

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
57308 2018-07-14T14:16:12 Z gabrielsimoes 여행하는 상인 (APIO17_merchant) C++17
0 / 100
 923 ms 10388 KB 
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
const int MAXN = 101, MAXM = 9901, MAXK = 1001;
const int MAXSUM = 10000;
// const int MAXN = 51, MAXK = 51;
const ll INF = 1e18;

int N, M, K;
vector<pii> g[MAXN];
ll buy[MAXN][MAXK];
ll sell[MAXN][MAXK];

ll d[MAXN][MAXN];
ll gain[MAXN][MAXN];

// ll dist[2][MAXN];
// priority_queue<pair<int, ll>, vector<pair<int, ll>>, greater<pair<int, ll>>> q;
// void dijkstra(int start, ll d[], vector<pii> g[]) {
//     for (int i = 1; i <= N; i++) d[i] = INF;
//     q.push({0, start});
//     d[start] = 0;

//     while (!q.empty()) {
//         ll dd; int cur;
//         tie(dd, cur) = q.top();
//         q.pop();
//         if (dd > d[cur]) continue;
//         for (pii p : g[cur]) {
//             int nx = p.first;
//             ll cost = p.second;

//             if (dd + cost < d[nx]) {
//                 d[nx] = dd + cost;
//                 q.push({d[nx], nx});
//             }
//         }
//     }
// }

ll dp[MAXN][MAXSUM];
bool ok[MAXN][MAXSUM];

ll f(int cur, int sum) {
    if (cur == 1 && sum == 0) return 0;
    else if (sum <= 0) return -INF;
    else if (d[cur][1] > sum) return -INF;

    ll &ret = dp[cur][sum];
    if (ok[cur][sum]) return ret;
    ok[cur][sum] = true;
    ret = -INF;

    for (int i = 1; i <= N; i++) {
        if (i != cur) {
            ret = max(ret, f(i, sum - d[cur][i]) + gain[cur][i]);
        }
    }

    return ret;
}

int main() {
    scanf("%d%d%d", &N, &M, &K);
    for (int i = 1; i <= N; i++) {
        for (int k = 1; k <= K; k++) {
            scanf("%lld%lld", &buy[i][k], &sell[i][k]);
        }
    }

    for (int i = 1; i <= N; i++) {
        for (int k = 1; k <= N; k++) {
            d[i][k] = INF;
        }
        d[i][i] = 0;
    }

    for (int i = 1,a,b,c; i <= M; i++) {
        scanf("%d%d%d", &a, &b, &c);
        g[a].push_back({b, c});
        d[a][b] = c;
    }

    for (int k = 1; k <= N; k++) {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            for (int k = 1; k <= K; k++) {
                if (buy[i][k] != -1 && sell[j][k] != -1) {
                    gain[i][j] = max(gain[i][j], -buy[i][k] + sell[j][k]);
                }
            }
        }
    }

    ll ans = 0;
    for (int sum = 1; sum < MAXSUM; sum++) {
        ans = max(ans, f(1, sum)/ll(sum));
    }

    // for (int sum = 0; sum <= N*N; sum++) {
    //     for (int i = 1; i <= N; i++) {
    //         printf("sum %d i %d: %lld\n", sum, i, f(i, sum));
    //     }
    // }

    // ll ans = 0;
    // for (int i = 1; i <= N; i++) {
    //     ll dist = d[1][i] + d[i][1];
    //     if (dist > 0)
    //         ans = max(ans, gain[1][i]/dist);
    // }

    printf("%lld\n", ans);
}

Compilation message

merchant.cpp: In function 'int main()':
merchant.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &N, &M, &K);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:69:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%lld%lld", &buy[i][k], &sell[i][k]);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:81:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &a, &b, &c);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 43 ms 2040 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 242 ms 5336 KB Output is correct
2 Incorrect 247 ms 5380 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 923 ms 10388 KB Output is correct
2 Incorrect 91 ms 10388 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 242 ms 5336 KB Output is correct
2 Incorrect 247 ms 5380 KB Output isn't correct
3 Halted 0 ms 0 KB -