oj.uz

Submission #50743

# Submission time Handle Problem Language Result Execution time Memory
50743 2018-06-13T06:38:57 Z ayhcbagnop Travelling Merchant (APIO17_merchant) C++14
0 / 100
 146 ms 1620 KB 
//Power Of Ninja Go
#include <bits/stdc++.h>
//#ifdef atom #else #endif
using namespace std;
typedef long long ll; typedef pair<int, int> ii; typedef vector<int> vi; typedef vector< ii > vii;
#define X first
#define Y second
#define pb push_back
const int maxn = 105;
const int maxk = 1005;
int dist[maxn][maxn];
int buy[maxn][maxk];
int sell[maxn][maxk];
ll prof[maxn][maxn];
ll aug[maxn][maxn];
int n, m, k;
bool works(ll x)
{
    //printf("x = %lld\n", x);
    for(int i = 1; i<= n; i++)
    {
        for(int j = 1; j<= n; j++)
        {
            aug[i][j] = 1LL*x*dist[i][j] - prof[i][j];
            //printf("aug[%d][%d] = %lld\n", i, j, aug[i][j]);
        }
    }
    for(int k = 1; k<= n; k++) for(int i = 1; i<= n; i++) for(int j = 1; j<= n; j++)
        aug[i][j] = min(aug[i][j], aug[i][k]+aug[k][j]);
    for(int i = 1; i<= n; i++) if(aug[i][i]<= 0) return true;
    return false;
}
int main()
{
    scanf("%d %d %d", &n, &m, &k);
    for(int i = 1; i<= n; i++) for(int j = 1; j<= n; j++) dist[i][j] = 1e9;
    for(int i = 1; i<= n; i++)
    {
        for(int j = 1; j<= k; j++) scanf("%d %d", &buy[i][j], &sell[i][j]);
    }
    while(m--)
    {
        int u, v, w; scanf("%d %d %d", &u, &v, &w);
        dist[u][v] = min(dist[u][v], w);
    }
    for(int k = 1; k<= n; k++) for(int i = 1; i<= n; i++) for(int j = 1; j<= n; j++) dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]);
    for(int i = 1; i<= n; i++) for(int j = 1; j<= n; j++) prof[i][j] = 0;
    for(int i = 1; i<= n; i++)
    {
        for(int j = 1; j<= n; j++)
        {
            for(int prod = 1; prod<= k; prod++)
            {
                if(buy[i][prod] == -1 || sell[j][prod] == -1) continue;
                prof[i][j] = max(prof[i][j], 1LL*sell[j][prod]-buy[i][prod]);
            }
            //printf("prof[%d][%d] = %lld\n", i, j, prof[i][j]);
        }
    }
    ll lo = 0, hi = 1e12;
    while(lo< hi)
    {
        ll mid = (lo+hi+1)/2;
        if(works(mid)) lo = mid;
        else hi = mid-1;
    }
    printf("%lld\n", lo);
}

Compilation message

merchant.cpp: In function 'int main()':
merchant.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &m, &k);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:39:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         for(int j = 1; j<= k; j++) scanf("%d %d", &buy[i][j], &sell[i][j]);
                                    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:43:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int u, v, w; scanf("%d %d %d", &u, &v, &w);
                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 12.0

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

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1400 KB Output is correct
2 Correct 11 ms 1400 KB Output is correct
3 Correct 10 ms 1400 KB Output is correct
4 Correct 10 ms 1400 KB Output is correct
5 Correct 15 ms 1400 KB Output is correct
6 Correct 3 ms 1400 KB Output is correct
7 Incorrect 12 ms 1400 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 1492 KB Output is correct
2 Correct 146 ms 1592 KB Output is correct
3 Correct 71 ms 1592 KB Output is correct
4 Incorrect 73 ms 1620 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1400 KB Output is correct
2 Correct 11 ms 1400 KB Output is correct
3 Correct 10 ms 1400 KB Output is correct
4 Correct 10 ms 1400 KB Output is correct
5 Correct 15 ms 1400 KB Output is correct
6 Correct 3 ms 1400 KB Output is correct
7 Incorrect 12 ms 1400 KB Output isn't correct
8 Halted 0 ms 0 KB -