oj.uz

Submission #225702

# Submission time Handle Problem Language Result Execution time Memory
225702 2020-04-21T10:34:00 Z LittleFlowers__ Travelling Merchant (APIO17_merchant) C++14
12 / 100
 711 ms 2812 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r){return l+rng()%(r-l+1);}
#define fasty ios_base::sync_with_stdio(0),cin.tie(0);
#define forinc(a,b,c) for(int a=b,_c=c;a<=_c;++a)
#define fordec(a,b,c) for(int a=b,_c=c;a>=_c;--a)
#define forv(a,b) for(auto&a:b)
#define fi first
#define se second
#define pb push_back
#define ii pair<int,int>
#define mt make_tuple
#define all(a) a.begin(),a.end()
#define reset(f, x) memset(f, x, sizeof(f))
#define bit(x,i) ((x>>(i-1))&1)
#define on(x,i) (x|(1ll<<(i-1)))
#define off(x,i) (x&~(1<<(i-1)))
#define gg exit(0);

const int N=110,
          K=1010,
          INF=1e15;

int n,m,k;
int buy[N][K],sell[N][K];
int to[N][N],inc[N][N];

struct pack{
    int m[101][101];
};

pack operator*(pack a,pack b){
    pack c;
    forinc(i,1,n) forinc(j,1,n) c.m[i][j]=-INF;
    forinc(t,1,n) forinc(i,1,n) forinc(j,1,n) c.m[i][j]=max(c.m[i][j],a.m[i][t]+b.m[t][j]);
    return c;
}

int chk(int val){
    pack tmp;
    forinc(i,1,n) forinc(j,1,n){
        if(to[i][j]<INF) tmp.m[i][j]=inc[i][j]-val*to[i][j];
        else tmp.m[i][j]=-INF;
    }
    forinc(tim,1,20) tmp=tmp*tmp;
    int ret=0;
    forinc(i,1,n) ret|=tmp.m[i][i]>=0;
    return ret;
}

main(){
    #define task "merchant"
    //freopen(task".inp","r",stdin);
    //freopen(task".out","w",stdout);

    n=in,m=in,k=in;
    forinc(i,1,n) forinc(j,1,k) buy[i][j]=in, sell[i][j]=in;
    forinc(i,1,n)  forinc(j,1,n) to[i][j]=INF;
    forinc(i,1,m){
        int u=in,v=in;
        to[u][v]=min(to[u][v],in);
    }
    forinc(t,1,n) forinc(i,1,n) forinc(j,1,n) to[i][j]=min(to[i][j],to[i][t]+to[t][j]);
    forinc(t,1,k) forinc(i,1,n) forinc(j,1,n) if(sell[j][t]>0 && buy[i][t]>0) inc[i][j]=max(inc[i][j],sell[j][t]-buy[i][t]);
    int le=1,mi,ri=1e9,ret=0;
    while(le<=ri){
        mi=(le+ri)/2;
        if(chk(mi)) ret=mi, le=mi+1; else ri=mi-1;
    }
    cout<<ret<<"\n";
}

Compilation message

merchant.cpp:54:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 657 ms 2660 KB Output is correct
2 Correct 667 ms 1536 KB Output is correct
3 Correct 662 ms 1584 KB Output is correct
4 Correct 99 ms 1024 KB Output is correct
5 Correct 100 ms 1024 KB Output is correct
6 Correct 101 ms 1024 KB Output is correct
7 Correct 106 ms 1272 KB Output is correct
8 Correct 12 ms 640 KB Output is correct
9 Correct 104 ms 1024 KB Output is correct
10 Correct 102 ms 1024 KB Output is correct
11 Correct 106 ms 1024 KB Output is correct
12 Correct 13 ms 640 KB Output is correct
13 Correct 102 ms 1152 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 1152 KB Output is correct
2 Correct 104 ms 1272 KB Output is correct
3 Correct 104 ms 1152 KB Output is correct
4 Correct 92 ms 1152 KB Output is correct
5 Correct 105 ms 1152 KB Output is correct
6 Correct 12 ms 640 KB Output is correct
7 Correct 109 ms 1152 KB Output is correct
8 Correct 100 ms 1152 KB Output is correct
9 Correct 105 ms 1272 KB Output is correct
10 Correct 104 ms 1152 KB Output is correct
11 Incorrect 111 ms 1152 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 670 ms 2044 KB Output is correct
2 Incorrect 711 ms 2812 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 1152 KB Output is correct
2 Correct 104 ms 1272 KB Output is correct
3 Correct 104 ms 1152 KB Output is correct
4 Correct 92 ms 1152 KB Output is correct
5 Correct 105 ms 1152 KB Output is correct
6 Correct 12 ms 640 KB Output is correct
7 Correct 109 ms 1152 KB Output is correct
8 Correct 100 ms 1152 KB Output is correct
9 Correct 105 ms 1272 KB Output is correct
10 Correct 104 ms 1152 KB Output is correct
11 Incorrect 111 ms 1152 KB Output isn't correct
12 Halted 0 ms 0 KB -