Submission #575463

#	Time	Username	Problem	Language	Result	Execution time	Memory
575463		AJ00	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	130 ms	4176 KiB

merchant

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
 
const ll INF = 1'000'000'001LL;
// const ll INF = 100;
 
int main()
{
    int N, M, K;
    cin >> N >> M >> K;
 
    vvll B(1+N, vll(1+K, INF));
    vvll S(1+N, vll(1+K, 0));
    for(int i = 1; i <= N; i++)
    {
        for(int j = 1; j <= K; j++)
        {
            ll b, s;
            cin >> b >> s;
            if(b != -1) B[i][j] = b;
            if(s != -1) S[i][j] = s;
        }
    }
 
    vvll dist(1+N, vll(1+N, INF));
    for(int i = 1; i <= N; i++) dist[i][i] = 0;
 
    for(int e = 1; e <= M; e++)
    {
        int V, W;
        ll T;
        cin >> V >> W >> T;
        dist[V][W] = min(dist[V][W], T);
    }
 
    for(int k = 1; k <= N; k++)
        for(int i = 1; i <= N; i++)
            for(int j = 1; j <= N; j++)
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
 
    vvll profit(1+N, vll(1+N, 0));
    for(int u = 1; u <= N; u++)
        for(int v = 1; v <= N; v++)
            for(int j = 1; j <= K; j++)
                profit[u][v] = max(profit[u][v], S[v][j] - B[u][j]);
 
    // cerr << "read\n";
    //
    // for(int u = 1; u <= N; u++)
    //     for(int v = 1; v <= N; v++)
    //         cerr << u << ' ' << v << " : " << dist[u][v] << ' ' << profit[u][v] << '\n';
 
    // for(int u = 1; u <= N; u++)
    //     for(int v = 1; v <= N; v++)
    //         cout << u << ' ' << v << ' ' << dist[u][v] << ' ' << profit[u][v] << '\n';
 
    ll basic_res = 0;
    for(int v = 2; v <= N; v++)
        basic_res = max(basic_res, profit[1][v]/(dist[1][v] + dist[v][1]));
    // cerr << "basic res = " << basic_res << '\n';
 
    // for(int v = 2; v <= N; v++) cerr << v << " : " << dist[1][v] << ' ' << dist[v][1] << ' ' << profit[1][v] << '\n';
 
 
    ll lo = 0, hi = INF;
    while(lo != hi)
    {
        // cerr << "\n\n\n\n\n\n";
        // cerr << lo << ' ' << hi << " :  ";
        ll aim = (lo+hi)/2 + 1;
        // cerr << aim << '\n';
 
        vvll newdist(1+N, vll(1+N, -INF*INF));
 
        for(int u = 1; u <= N; u++)
            for(int v = 1; v <= N; v++)
                newdist[u][v] = max(newdist[u][v], profit[u][v] - aim*dist[u][v]);
 
        for(int k = 1; k <= N; k++)
            for(int i = 1; i <= N; i++)
                for(int j = 1; j <= N; j++)
                {
                    newdist[i][j] = max({newdist[i][j], min(INF*INF, newdist[i][k] + newdist[k][j]), -INF*INF});
                }
 
        // for(int v = 2; v <= N; v++)
        //     cerr << v << " : " << newdist[1][v] << ' ' << newdist[v][1] << '\n';
 
        // cerr << "\n\n\n\n\n searching " << aim << '\n';
        // for(int u = 1; u <= N; u++)
        //     for(int v = 1; v <= N; v++)
        //         cerr << u << ' ' << v << " : " << newdist[u][v] << '\n';
 
        ll mx = -1;
 
        for(int u = 1; u <= N; u++)
            for(int v = u+1; v <= N; v++)
                mx = max(mx, newdist[u][v] + newdist[v][u]);
 
        if(mx >= 0)
            lo = aim;
        else
            hi = aim-1;
    }
 
    cout << lo << '\n';
}

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