Submission #403285

#	Time	Username	Problem	Language	Result	Execution time	Memory
403285		Haruto810198	Travelling Merchant (APIO17_merchant)	C++17	12 / 100	26 ms	3248 KiB

merchant

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double

#define FOR(i,l,r,d) for(int i=(l);i<=(r);i+=(d))
#define szof(x) ((x).size())

#define vi vector<int>
#define pii pair<int,int>

#define F first
#define S second

#define pb push_back
#define eb emplace_back
#define mkp make_pair

const int INF = 2147483647;
const int MOD = 1000000007;
const int mod = 998244353;
const double eps = 1e-12;

//#pragma GCC optimize("Ofast")

const int NMAX = 101;
const int MMAX = 9901;
const int CMAX = 1001;
/// c = n. of items

int n, m, c;
int edge[101][101];
int dis[101][101];

int buy[NMAX][CMAX], sell[NMAX][CMAX];
/// buy[][] : buy item j at market i

int res;

void FW(){
    FOR(k,1,n,1){
        FOR(i,1,n,1){
            FOR(j,1,n,1){
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
            }
        }
    }
}

signed main(){

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    /// input
    cin>>n>>m>>c;

    FOR(i,1,n,1){
        FOR(j,1,c,1){
            cin>>buy[i][j]>>sell[i][j];
        }
    }

    FOR(i,1,n,1){
        FOR(j,1,n,1){
            edge[i][j] = INF*INF;
        }
    }
    FOR(i,1,m,1){
        int u, v, w;
        cin>>u>>v>>w;
        edge[u][v] = w;
    }

    FOR(i,1,n,1){
        FOR(j,1,n,1){
            dis[i][j] = edge[i][j];
        }
    }

    /// all-pair SP
    FW();

    /// init res
    res = 0;

    /// enumerate (destination i, item j)
    FOR(i,1,n,1){
        FOR(j,1,c,1){
            int lc = dis[1][i] + dis[i][1]; /// len. of cycle
            int pf = -buy[1][j] + sell[i][j]; /// profit
            res = max(res, pf/lc);
        }
    }

    cout<<res<<'\n';

    return 0;

}

• Subtask 1: 12 / 12
• Subtask 2: 0 / 21
• Subtask 3: 0 / 33
• Subtask 4: 0 / 34