oj.uz

Submission #984303

# Submission time Handle Problem Language Result Execution time Memory
984303 2024-05-16T12:58:14 Z Unforgettablepl Travelling Merchant (APIO17_merchant) C++17
0 / 100
 62 ms 3932 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int INF = 1e18;

pair<int,int> dist[101][101];
int buy[101][1001];
int sell[101][1001];
int n;

bool check(int x){
    vector<vector<int>> adj(n+1,vector<int>(n+1));
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){
        adj[i][j] = x*dist[i][j].first - dist[i][j].second;
    }
    for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){
        adj[i][j] = min(adj[i][j],adj[i][k]+adj[k][j]);
    }
    for(int i=1;i<=n;i++)if(adj[i][i]<=0)return true;
    return false;
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int m,l;
    cin >> n >> m >> l;
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)dist[i][j].first=INF;
//    for(int i=1;i<=n;i++)dist[i][i].first=0;
    for(int i=1;i<=n;i++)for(int j=1;j<=l;j++)cin>>buy[i][j]>>sell[i][j];
    for(int i=1;i<=m;i++){
        int u,v,t;cin>>u>>v>>t;
        dist[u][v].first = 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].first = min(dist[i][j].first,dist[i][k].first+dist[k][j].first);
    }
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){
        for(int item=1;item<=l;item++){
            if(buy[i][item]==-1 or sell[j][item]==-1)continue;
            dist[i][j].second = max(dist[i][j].second,sell[j][item]-buy[i][item]);
        }
    }
    int ans = 0;
    for(int jump=536870912ll;jump;jump/=2){
        if(check(ans+jump))ans+=jump;
    }
    cout << ans << '\n';
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 3424 KB Output is correct
2 Correct 28 ms 1620 KB Output is correct
3 Correct 28 ms 1372 KB Output is correct
4 Correct 4 ms 856 KB Output is correct
5 Correct 5 ms 860 KB Output is correct
6 Correct 5 ms 860 KB Output is correct
7 Correct 4 ms 860 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 4 ms 860 KB Output is correct
10 Correct 4 ms 860 KB Output is correct
11 Correct 4 ms 860 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Incorrect 4 ms 860 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 860 KB Output is correct
2 Correct 4 ms 860 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 4 ms 860 KB Output is correct
5 Correct 4 ms 860 KB Output is correct
6 Correct 4 ms 860 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 4 ms 860 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 1628 KB Output is correct
2 Correct 62 ms 3932 KB Output is correct
3 Correct 37 ms 1876 KB Output is correct
4 Correct 39 ms 1624 KB Output is correct
5 Correct 30 ms 1628 KB Output is correct
6 Correct 29 ms 1624 KB Output is correct
7 Correct 6 ms 856 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 4 ms 996 KB Output is correct
10 Correct 4 ms 860 KB Output is correct
11 Incorrect 4 ms 860 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 1628 KB Output is correct
2 Correct 62 ms 3932 KB Output is correct
3 Correct 37 ms 1876 KB Output is correct
4 Correct 39 ms 1624 KB Output is correct
5 Correct 30 ms 1628 KB Output is correct
6 Correct 29 ms 1624 KB Output is correct
7 Correct 6 ms 856 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 4 ms 996 KB Output is correct
10 Correct 4 ms 860 KB Output is correct
11 Incorrect 4 ms 860 KB Output isn't correct
12 Halted 0 ms 0 KB -