Submission #736675

#	Time	Username	Problem	Language	Result	Execution time	Memory
736675		baokhue232005	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	81 ms	12740 KiB

merchant

/*
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
*/
// lethal option
//  #pragma GCC optimize ("trapv")

#include<bits/stdc++.h>
using namespace std;

#define all(flg) flg.begin(), flg.end()
#define int long long
#define pb push_back
#define fi first
#define se second
#define endl "\n"
#define eb emplace_back
#define ii pair<int, int>
#define vi vector<int>
#define PI 3.141592653589793238462643383279502884
#define ll long long
#define ld long double
#define for1(i, ff, gg) for(int i = ff; i <= gg; ++i)
#define for2(i, ff, gg) for(int i = ff; i >= gg; --i)
const ll mod = 1e9 + 7;
const int maxN = 1005;
const ll oo = 1e18 + 7;
int n, a[maxN];
int x, y, z, k, m;

int table[maxN][maxN];
int origin[maxN][maxN];
int b[maxN][maxN];
int s[maxN][maxN];

void floyd(){
    for1(i, 1, n){
        for1(j, 1, n) for1(k, 1, n){
            table[j][k] = min(table[j][k], table[j][i] + table[i][k]);
        }
    }
}

int protrade[maxN][maxN];

bool solve(int multer){
    for1(i, 1, n) for1(j, 1, n){
        table[i][j] = origin[i][j] * multer - protrade[i][j];
        if(oo / multer < origin[i][j]) table[i][j] = oo;
    }
    for1(i, 1, n) table[i][i] = oo;
    floyd();
    for1(i, 1, n) if(table[i][i] <= 0) return 1;
    return 0;
}

signed main(){
    // freopen(".inp", "r", stdin);
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> m >> k;
    for1(i, 1, n){
        for1(j, 1, k){
            cin >> b[i][j] >> s[i][j];
            if(b[i][j] == -1) b[i][j] = mod;
            if(s[i][j] == -1) s[i][j] = 0;

        }
    }
    memset(table, 15, sizeof(table));
    while(m--){
        cin >> x >> y >> z;
        table[x][y] = z;
    }
    for1(i, 1, n) table[i][i] = 0;
    floyd();
    for1(i, 1, n) for1(j, 1, n) origin[i][j] = table[i][j];
    for1(i, 1, n) for1(j, 1, n){
        int val = 0;
        for1(g, 1, k) val = max(val, s[j][g] - b[i][g]);
        protrade[i][j] = val;
    }
    int lb = 0, rb = mod;
    while(lb != rb){
        int mid = (lb + rb + 1) / 2;
        if(solve(mid)) lb = mid;
        else rb = mid - 1;
    }
    cout << lb << endl;
}

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