oj.uz

Submission #166480

# Submission time Handle Problem Language Result Execution time Memory
166480 2019-12-02T15:12:01 Z combi1k1 Travelling Merchant (APIO17_merchant) C++14
0 / 100
 113 ms 1784 KB 
#include<bits/stdc++.h>

using namespace std;

#define ll  long long

int s[101][1000];
int b[101][1000];
int d[101][101];
int w[101][101];

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;  cin >> n;
    int m;  cin >> m;
    int k;  cin >> k;

    for(int i = 0 ; i < n ; ++i)
    for(int j = 0 ; j < k ; ++j)
        cin >> b[i][j],
        cin >> s[i][j];

    memset(d,0x3f,sizeof d);

    for(int i = 0 ; i < n ; ++i)    d[i][i] = 0;
    for(int i = 0 ; i < m ; ++i)    {
        int x;  cin >> x;   --x;
        int y;  cin >> y;   --y;
        int t;  cin >> t;
        d[x][y] = t;
    }

    for(int T = 0 ; T < n ; ++T)
    for(int i = 0 ; i < n ; ++i)
    for(int j = 0 ; j < n ; ++j)
        d[i][j] = min(d[i][j],d[i][T] + d[T][j]);

    for(int P = 0 ; P < k ; ++P)
    for(int i = 0 ; i < n ; ++i)
    for(int j = 0 ; j < n ; ++j)    if (b[i][P] >= 0 && s[j][P] >= 0)
        w[i][j] = max(w[i][j],s[j][P] - b[i][P]);

    vector<vector<ll> > dd(n,vector<ll>(n));

    int l = 0;
    int r = 1e9 + 7;

    for(; l + 1 < r ;)  {
        m = (l + r) / 2;
        for(int i = 0 ; i < n ; ++i)
        for(int j = 0 ; j < n ; ++j)
            dd[i][j] = w[i][j] - 1ll * m * d[i][j];

        for(int T = 0 ; T < n ; ++T)
        for(int i = 0 ; i < n ; ++i)
        for(int j = 0 ; j < n ; ++j)
            dd[i][j] = max(dd[i][j],dd[i][T] + dd[T][j]);

        bool ok = 0;

        for(int i = 0 ; i < n ; ++i)
        for(int j = 0 ; j < n ; ++j)    if (i != j && dd[i][j] + dd[j][i] >= 0)
            ok = 1;

        if (ok) l = m;
        else    r = m;
    }
    cout << l << endl;
}
/*
4 5 2
10 9 5 2
6 4 20 15
9 7 10 9
-1 -1 16 11
1 2 3
2 3 3
1 4 1
4 3 1
3 1 1
*/

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 1784 KB Output is correct
2 Correct 47 ms 1336 KB Output is correct
3 Incorrect 113 ms 1400 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 760 KB Output is correct
2 Correct 8 ms 888 KB Output is correct
3 Correct 11 ms 760 KB Output is correct
4 Correct 8 ms 888 KB Output is correct
5 Correct 9 ms 888 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 8 ms 888 KB Output is correct
8 Correct 9 ms 888 KB Output is correct
9 Correct 9 ms 888 KB Output is correct
10 Correct 9 ms 888 KB Output is correct
11 Correct 10 ms 888 KB Output is correct
12 Correct 9 ms 888 KB Output is correct
13 Incorrect 9 ms 808 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

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

Subtask #4
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 760 KB Output is correct
2 Correct 8 ms 888 KB Output is correct
3 Correct 11 ms 760 KB Output is correct
4 Correct 8 ms 888 KB Output is correct
5 Correct 9 ms 888 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 8 ms 888 KB Output is correct
8 Correct 9 ms 888 KB Output is correct
9 Correct 9 ms 888 KB Output is correct
10 Correct 9 ms 888 KB Output is correct
11 Correct 10 ms 888 KB Output is correct
12 Correct 9 ms 888 KB Output is correct
13 Incorrect 9 ms 808 KB Output isn't correct
14 Halted 0 ms 0 KB -