oj.uz

Submission #85068

# Submission time Handle Problem Language Result Execution time Memory
85068 2018-11-18T11:37:05 Z popovicirobert Travelling Merchant (APIO17_merchant) C++14
0 / 100
 1000 ms 6420 KB 
#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long

using namespace std;

const ll INF = 1e18;
const int MAXN = 100;
const int MAXK = 1000;

double t_start;

vector < pair <int, int> > g[MAXN + 1];
int buy[MAXN + 1][MAXK + 1], sell[MAXN + 1][MAXK + 1];

vector <int> b[MAXN + 1], s[MAXN + 1];

ll dp[MAXN + 1][MAXK + 1];
int n, m, k;

bool inq[MAXN + 1][MAXK + 1];

inline bool check(int delta) {
    for(int start = 1; start <= n; start++) {
        int i, j;
        for(i = 1; i <= n; i++) {
            for(j = 0; j <= k; j++) {
                dp[i][j] = -INF;
                inq[i][j] = 0;
            }
        }
        bool ok = 0;
        queue < pair <int, int> > Q;
        Q.push({start, 0});
        dp[start][0] = 0;
        while(!Q.empty() && !ok) {
            int nod = Q.front().first;
            int obj = Q.front().second;
            inq[nod][obj] = 0;
            Q.pop();
            if(dp[start][0] > 0) {
                return 1;
            }
            if(obj == 0) {
                for(auto o : b[nod]) {
                    ll cur = dp[nod][0] - buy[nod][o];
                    if(dp[nod][o] < cur) {
                        dp[nod][o] = cur;
                        if(!inq[nod][o]) {
                            Q.push({nod, o});
                            inq[nod][o] = 1;
                        }
                    }
                    else if(dp[nod][o] == cur && nod == start && o == 0) {
                        ok = 1;
                    }
                }
            }
            for(auto it : g[nod]) {
                ll cur = dp[nod][obj] - 1LL * it.second * delta + sell[it.first][obj];
                if(sell[it.first][obj] > -1) {
                    if(dp[it.first][0] < cur) {
                        dp[it.first][0] = cur;
                        if(!inq[it.first][0]) {
                            inq[it.first][0] = 1;
                            Q.push({it.first, 0});
                        }
                    }
                    else if(dp[it.first][0] == cur && it.first == start) {
                        ok = 1;
                    }
                }
                cur = dp[nod][obj] - 1LL * delta * it.second;
                if(cur > dp[it.first][obj]) {
                    dp[it.first][obj] = cur;
                    if(!inq[it.first][obj]) {
                        inq[it.first][obj] = 1;
                        Q.push({it.first, obj});
                    }
                }
                else if(dp[it.first][obj] == cur && it.first == start && obj == 0) {
                    ok = 1;
                }
            }
        }
        if(ok) {
            return 1;
        }
        /*if((clock() - t_start) / CLOCKS_PER_SEC > 0.9) {
            return ans;
        }*/
    }
    return 0;
}

int main() {
    //ifstream cin("C.in");
    //ofstream cout("C.out");
    int i, j;
    ios::sync_with_stdio(false);
    //t_start = clock();
    cin >> n >> m >> k;
    for(i = 1; i <= n; i++) {
        for(j = 1; j <= k; j++) {
            cin >> buy[i][j] >> sell[i][j];
            if(buy[i][j] > -1) {
                b[i].push_back(j);
            }
            /*if(sell[i][j] > -1) {
                s[i].push_back(j);
            }*/
        }
    }
    for(i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
    }
    int delta = 0;
    for(int step = 1 << 29; step; step >>= 1) {
        if(check(delta + step)) {
            delta += step;
        }
    }
    cout << delta;
    //cin.close();
    //cout.close();
    return 0;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1093 ms 3480 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 3480 KB Output is correct
2 Execution timed out 1093 ms 3480 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 582 ms 3480 KB Output is correct
2 Execution timed out 1059 ms 6420 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 3480 KB Output is correct
2 Execution timed out 1093 ms 3480 KB Time limit exceeded
3 Halted 0 ms 0 KB -