Submission #759276

#	Time	Username	Problem	Language	Result	Execution time	Memory
759276		boyliguanhan	Travelling Merchant (APIO17_merchant)	C++17	0 / 100	445 ms	1812 KiB

merchant

#include<bits/stdc++.h>
#define int long long
#define X(z) x[z][i][j]
#define L F(i,n)F(j,n)
#define F(x,y) for(int x=1;x<=y;++x)
using namespace std;
int n,m,K,x[4][101][101];
void xxx(){}
bool C(int t) {
    L X(3)=-1e18;
    L {
        if(i==4&&j==3) xxx();
        if(i==j||X(0)>1e9)continue;
        X(3)=-t*X(0);
        F(k,K) {
            if(x[1][i][k]<0||x[2][j][k]<0)continue;
            X(3)=max(X(3),x[2][j][k]-x[1][i][k]-t*X(0));
        }
    }
    F(k,n)L X(3)=max(X(3),x[3][i][k]+x[3][k][j]);
    F(i,n) if(x[3][i][i]>=0)return 1;
    return 0;
}
signed main() {
    cin >> n >> m >> K;
    L X(0)=2e9;
    F(i,n){
        F(j,K)cin>>X(1);
        F(j,K)cin>>X(2);
    }
    F(i,m){
        int a,b,c;
        cin>>a>>b>>c;
        x[0][a][b]=c;
    }
    F(k,n)L X(0)=min(X(0),x[0][i][k]+x[0][k][j]);
    int l=0,r=1e9;
    while(l<r){
        if(C(l+r+1>>1)) {
            l = l+r+1>>1;
        } else {
            r = l+r-1>>1;
        }
    }
    cout << max(l,0ll)<< '\n';
}

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:39:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |         if(C(l+r+1>>1)) {
      |              ~~~^~
merchant.cpp:40:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |             l = l+r+1>>1;
      |                 ~~~^~
merchant.cpp:42:20: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   42 |             r = l+r-1>>1;
      |                 ~~~^~

• Subtask 1: 0 / 12
• Subtask 2: 0 / 21
• Subtask 3: 0 / 33
• Subtask 4: 0 / 34