oj.uz

Submission #955534

# Submission time Handle Problem Language Result Execution time Memory
955534 2024-03-30T21:36:10 Z Matjaz Travelling Merchant (APIO17_merchant) C++14
0 / 100
 107 ms 2900 KB 
//
//  APIO17_MERCHANT.cpp
//  
//
//  Created by Matjaz Leonardis on 22/03/2024.
//

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N,M,K;
long long INF = (1LL<<39);

// If we buy something at u and go to v there will be the perfect item for that and we can take the shortest path there. 

int main(){
    cin >> N >> M >> K;
    
    vector<vector<int> > B(N, vector<int> (K));
    vector<vector<int> > S(N, vector<int> (K));
    
    for (int i=0;i<N;i++){
        for (int j=0;j<K;j++) cin >> B[i][j] >> S[i][j];
    }
    
    vector<vector<long long> > dist(N, vector<long long>(N, INF));
    
    for (int i=0;i<M;i++){
        int V,W,T;
        cin >> V >> W >> T;
        dist[V - 1][W - 1] = T;
    }
    
    for (int k=0;k<N;k++){
        for (int i=0;i<N;i++){
            for (int j=0;j<N;j++) dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
        }
    }
    
    /*cout << "OG" << endl;
    for (int i=0;i<N;i++){
        for (int j=0;j<N;j++) cout << dist[i][j] << " ";
        cout << endl;
    }
    cout << endl; */
    
    vector<vector<long long> > profit(N, vector<long long> (N));
    
    for (int i=0;i<N;i++){
        for (int j=0;j<N;j++){
            for (int k=0;k<K;k++) if (B[i][k] >= 0) profit[i][j] = max(profit[i][j], (long long)S[j][k] - B[i][k]);
        }
    }
    
    /*cout << "Profit" << endl;
    for (int i=0;i<N;i++){
        for (int j=0;j<N;j++) cout << profit[i][j] << " ";
        cout << endl;
    }
    cout << endl; */
    
    
    
    long long best = 0;
    
    long long l = 0;
    long long u = 1e9;
    
    while (l < u){
        long long mid = l + (u - l + 1) / 2;
        // Each new edge is profit[i][j] - mid * dist[i][j]
        
        vector<vector<long long> > dist_tmp(N, vector<long long>(N, INF));
        
        for (int i=0;i<N;i++){
            for (int j=0;j<N;j++) dist_tmp[i][j] = mid * dist[i][j] - profit[i][j]; // Do we get any blow ups here?
        }
        
       /* cout << mid << endl;
        for (int i=0;i<N;i++){
            for (int j=0;j<N;j++) cout << dist_tmp[i][j] << " ";
            cout << endl;
        }
        cout << endl; */
        for (int k=0;k<N;k++){
            for (int i=0;i<N;i++){
                for (int j=0;j<N;j++) dist_tmp[i][j] = min(dist_tmp[i][j],dist_tmp[i][k] + dist_tmp[k][j]);
            }
        }
        
        /*cout << mid << endl;
        for (int i=0;i<N;i++){
            for (int j=0;j<N;j++) cout << dist_tmp[i][j] << " ";
            cout << endl;
        }
        cout << endl;*/
        
        bool contains_cycle = false;
        
        for (int i=0;i<N;i++) if (dist_tmp[i][i] <= 0) contains_cycle = true;
        
        if (contains_cycle) l = mid; else u = mid - 1;
    
    }
    
    best = l;
    cout << best << endl;
    
    return 0;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 2708 KB Output is correct
2 Correct 26 ms 600 KB Output is correct
3 Correct 28 ms 604 KB Output is correct
4 Correct 4 ms 344 KB Output is correct
5 Correct 4 ms 348 KB Output is correct
6 Correct 3 ms 348 KB Output is correct
7 Correct 5 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 4 ms 348 KB Output is correct
10 Correct 4 ms 348 KB Output is correct
11 Correct 4 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Incorrect 5 ms 344 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

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

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 876 KB Output is correct
2 Correct 107 ms 2900 KB Output is correct
3 Correct 30 ms 600 KB Output is correct
4 Correct 35 ms 980 KB Output is correct
5 Correct 35 ms 732 KB Output is correct
6 Correct 30 ms 888 KB Output is correct
7 Correct 5 ms 348 KB Output is correct
8 Correct 0 ms 352 KB Output is correct
9 Correct 7 ms 352 KB Output is correct
10 Correct 5 ms 352 KB Output is correct
11 Incorrect 5 ms 516 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 876 KB Output is correct
2 Correct 107 ms 2900 KB Output is correct
3 Correct 30 ms 600 KB Output is correct
4 Correct 35 ms 980 KB Output is correct
5 Correct 35 ms 732 KB Output is correct
6 Correct 30 ms 888 KB Output is correct
7 Correct 5 ms 348 KB Output is correct
8 Correct 0 ms 352 KB Output is correct
9 Correct 7 ms 352 KB Output is correct
10 Correct 5 ms 352 KB Output is correct
11 Incorrect 5 ms 516 KB Output isn't correct
12 Halted 0 ms 0 KB -