oj.uz

Submission #229170

# Submission time Handle Problem Language Result Execution time Memory
229170 2020-05-03T14:48:22 Z laoriu Travelling Merchant (APIO17_merchant) C++14
0 / 100
 101 ms 3064 KB 
#include <bits/stdc++.h>
using namespace std;
const double ll=1e-9;
typedef pair <int,int> pp;
int n,m,k,S[102][1002],B[102][1002];
int c[102][102],d[102][102];
double cost[102][102],s[102];
vector <pp> A[102];
void prepare()
{
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
        {
            c[i][j]=0;
            for (int x=1;x<=k;x++)
                if (B[i][x]!=-1&&S[j][x]!=-1) c[i][j]=max(c[i][j],S[j][x]-B[i][x]);
        }
    for (int x=1;x<=n;x++)
        for (int i=1;i<=n;i++)
            for (int j=1;j<=n;j++)
                d[i][j]=min(d[i][j],d[i][x]+d[x][j]);
    //for (int i=1;i<=n;i++)
       // for (int j=1;j<=n;j++)
       // cout<<i<<' '<<j<<' '<<d[i][j]<<' '<<c[i][j]<<endl;
}
int check(int x)
{
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            if (i!=j) cost[i][j]=(double) x*d[i][j]-c[i][j]-ll;
   /* cout<<"cac "<<x<<endl;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            cout<<i<<' '<<j<<' '<<cost[i][j]<<endl;*/
    for (int i=1;i<=n;i++)
        s[i]=cost[1][i];
    for (int x=1;x<=n;x++)
        for (int i=1;i<=n;i++)
            for (int j=1;j<=n;j++)
                if (s[j]>s[i]+cost[i][j]) s[j]=s[i]+cost[i][j];
    for (int i=1;i<=n;i++)
            for (int j=1;j<=n;j++)
                if (s[j]>s[i]+cost[i][j]) return 1;
    return 0;
}
void solve()
{
    //cout<<fixed<<setprecision(10)<<ll<<endl;
    cin>>n>>m>>k;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=k;j++)
        cin>>B[i][j]>>S[i][j];
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            if (i!=j) d[i][j]=1e9;
    for (int i=1;i<=m;i++)
    {
        int a,b,c;cin>>a>>b>>c;
        A[a].push_back({b,c});
        d[a][b]=min(d[a][b],c);
    }
    prepare();
    int d=0;int c=1e9;
    int res=0;
    while (d<=c)
    {
        int mid=(d+c)/2;
        if (check(mid)) {res=mid;d=mid+1;}
        else c=mid-1;
    }
    cout<<res;
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("merchant.inp","r",stdin);
    //freopen("merchant.out","w",stdout);
    solve();
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 2560 KB Output is correct
2 Correct 37 ms 1280 KB Output is correct
3 Correct 39 ms 1280 KB Output is correct
4 Correct 9 ms 768 KB Output is correct
5 Correct 10 ms 768 KB Output is correct
6 Correct 11 ms 896 KB Output is correct
7 Correct 11 ms 896 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 10 ms 896 KB Output is correct
10 Incorrect 10 ms 896 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

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

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 1632 KB Output is correct
2 Correct 101 ms 3064 KB Output is correct
3 Correct 43 ms 1408 KB Output is correct
4 Correct 48 ms 1536 KB Output is correct
5 Correct 45 ms 1536 KB Output is correct
6 Correct 43 ms 1408 KB Output is correct
7 Correct 11 ms 896 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 11 ms 928 KB Output is correct
10 Incorrect 11 ms 896 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 34.0

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