oj.uz

Submission #684430

# Submission time Handle Problem Language Result Execution time Memory
684430 2023-01-21T07:07:46 Z ar88lo Travelling Merchant (APIO17_merchant) C++14
0 / 100
 62 ms 3276 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int  INF = 1e9+1;
int n,m,k;
int dis[101][101], adj[101][101], adj2[101][101], prof[101][101];
int s[101][1001],b[101][1001];

bool check(int c){

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            adj2[i][j] = prof[i][j] - c * adj[i][j];
            if(adj[i][j] == INF) adj2[i][j] = c * INF;
        }
    }

    for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ dis[i][j] = adj2[i][j];}}

    for(int x = 1; x <= n; x++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(dis[i][x] < c * INF && dis[x][j] < c * INF) dis[i][j] = min(dis[i][j], dis[i][x] + dis[x][j]);
            }
        }
    }
    for(int i = 1; i <= n; i++){
        if(dis[i][i] >= 0) return 1;
    }
    return 0;
}
int32_t main(){

    cin>>n>>m>>k;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < k; j++){
            cin>>b[i][j]>>s[i][j];
        }
    }

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            adj[i][j] = INF;
        }
    }
    for(int i = 0; i < m; i++){
        int u,v,w;
        cin>>u>>v>>w;
        adj[u][v] = w;
    }

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            for(int x = 0; x < k; x++){
                if(s[j][x] != -1 && b[i][x] != -1){
                    prof[i][j] = max(prof[i][j], s[j][x] - b[i][x]);
                }
            }
        }
    }

    int ans = -1;
    for(int x = 1e9; x > 0; x/=2){
        while(ans + x < 1e9 && check(ans+x)) ans+=x;
    }
    cout<<ans + 1<<'\n';
    return 0;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 62 ms 3276 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 824 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 42 ms 1692 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 824 KB Output isn't correct
2 Halted 0 ms 0 KB -