Submission #905879

#	Time	Username	Problem	Language	Result	Execution time	Memory
905879		dimashhh	Travelling Merchant (APIO17_merchant)	C++17	0 / 100	36 ms	4176 KiB

merchant

#include <bits/stdc++.h>
using namespace std;
const int N = 100 + 1, MOD = 1e9 + 7;
typedef long long ll;
#define int long long
int n,m,k,b[N][1001],s[N][1001];
vector<pair<int,int>> g[N],gt[N][N];
vector<int> ord;
ll dp[N],val[N][N];
int ok[N][N],timer = 0,used[N],curv = 1,cost[101][101];
void dfs(int v){
    used[v] = timer;
    for(auto [to,w]:g[v]){
        if(used[to] != timer){
            gt[curv][v].push_back({to,w});
            dfs(to);
        }else{
            if(to == curv){
                // cout << curv << ' ' << v << '\n';
                ok[curv][v] = 1;
                val[curv][v] = w;
            }
        }
    }
}
int mid;
ll res = -1e18;
void dfs1(int v,ll cur,vector<int> &prs){
    for(int j:prs){
        dp[v] = max(dp[v],dp[j] + cost[j][v]);
    }
    if(ok[curv][v]){
        for(int j:prs){
            dp[v] = max(dp[v],dp[j] + cost[j][1]);
        }
        dp[v] = max(0ll,cost[v][1]) + dp[v];
        res = max(res,dp[v] - (cur + val[curv][v]) * mid);
        // cout << curv << ' ' << v << ' ' << dp[v] << ' ' <<  (cur + val[curv][v]) * mid << '\n';
    }
    for(auto [to,w]:gt[curv][v]){
        prs.push_back(v);
        dfs1(to,cur + w,prs);
        prs.pop_back();
    }
}
bool check(){
    res = -1e18;
    for(curv = 1;curv <= n;curv++){
        for(int i = 1;i <=n;i++){
            dp[i] = 0;
        }
        vector<int> em;
        dfs1(curv,0,em);
    }
    return (res >= 0);
}
void test(){
    cin >> n >> m >> k;
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= k;j++){
            cin >> b[i][j] >> s[i][j];
        }
    }
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= n;j++){
            if(i == j) continue;
            cost[i][j] = -1e18;
            for(int f = 1;f <= k;f++){
                if(b[i][f] != -1 && s[j][f] != -1){
                    cost[i][j] = max(cost[i][j],s[j][f]-b[i][f]);
                }
            }
        }
    }
    for(int i = 1;i <= m;i++){
        int x,y,w;
        cin >> x >> y >> w;
        g[x].push_back({y,w});
    }
    for(;curv <= n;curv++){
        ++timer;
        dfs(curv);
    }
    ll l = 0,r = 1e9;
    while(r - l > 1){
        mid = (l + r) >> 1;
        if(check()){
            l = mid;
        }else{
            r = mid;
        }
    }
    cout << l;
}
main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T = 1;
    // cin >> T;
    while (T--)
        test();
}

Compilation message (stderr)

merchant.cpp:95:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   95 | main()
      | ^~~~

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