제출 #469911

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
469911		ymm	여행하는 상인 (APIO17_merchant)	C++17	100 / 100	152 ms	4440 KiB

merchant

///
///   ♪ Pizza mozzarella rella rella rella... ♪
///

#define _USE_MATH_DEFINES
#define FAST ios::sync_with_stdio(false),cin.tie(0);
#include <bits/stdc++.h>
#define Loop(x, l, r) for(int x = (l); x < (r); ++x)
#define LoopR(x, l, r) for(int x = (r)-1; x >= (l); --x)
#define all(x) x.begin(), x.end()
#define Kill(x) exit((cout << (x) << '\n', 0))
#define YN(flag) ((flag)? "YES": "NO")
#define F first
#define S second
typedef           __int128   ll;
typedef unsigned long long  ull;
typedef std::pair<int,int>  pii;
typedef std::pair<ll ,ll >  pll;
using namespace std;

const int N = 103, K = 1003;
const ll inf = 1e18+10;
int n, m, k;
ll A1[N][N], A2[N][N], A3[N][N];
long long S[N][K], B[N][K];

int main()
{
    FAST;
    cin >> n >> m >> k;
    Loop(i,0,n) Loop(j,0,k) cin >> B[i][j] >> S[i][j];
    Loop(i,0,n) Loop(j,0,n) A1[i][j] = inf;
    Loop(i,0,n) A1[i][i] = 0;
    Loop(i,0,m)
    {
        int v, u, w;
        cin >> v >> u >> w;
        --v; --u;
        A1[v][u] = w;
    }
    Loop(k,0,n) Loop(i,0,n) Loop(j,0,n)
        A1[i][j] = min(A1[i][j], A1[i][k]+A1[k][j]);
    Loop(i,0,n) Loop(j,0,n) Loop(z,0,k)
        if(~S[j][z] && ~B[i][z]) A2[i][j] = max(A2[i][j], (ll)S[j][z]-B[i][z]);
    //Loop(i,0,n) {Loop(j,0,n) cout << (long long)A2[i][j] << ' '; cout << '\n';}
    ll l = 0, r = 1e9+10;
    while(l<r)
    {
        ll m = (l+r+1)/2;
        Loop(i,0,n) Loop(j,0,n) A3[i][j] = i==j?0:1000*(A2[i][j]-m*A1[i][j])+1;
        //Loop(i,0,n) {Loop(j,0,n) cout << (long long)A3[i][j] << ' '; cout << '\n';}
        Loop(k,0,n) Loop(i,0,n) Loop(j,0,n)
            A3[i][j] = max(A3[i][j], A3[i][k]+A3[k][j]);
        bool flg=0;
        Loop(i,0,n) flg |= A3[i][i];
        //Loop(i,0,n) cout << (long long)A3[i][i] << ' ';
        if(flg) l = m;
        else    r = m-1;
    }
    cout << (long long)l << '\n';
}

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