fork download
#include <bits/stdc++.h>

using namespace std;

typedef long double DOUBLE;
typedef vector<DOUBLE> VD;
typedef vector<VD> VVD;
typedef vector<int> VI;

const DOUBLE EPS = 1e-9;

struct LPSolver {
  int m, n;
  VI B, N;
  VVD D;

  LPSolver(const VVD &A, const VD &b, const VD &c) :
    m(b.size()), n(c.size()), N(n + 1), B(m), D(m + 2, VD(n + 2)) {
    for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) D[i][j] = A[i][j];
    for (int i = 0; i < m; i++) { B[i] = n + i; D[i][n] = -1; D[i][n + 1] = b[i]; }
    for (int j = 0; j < n; j++) { N[j] = j; D[m][j] = -c[j]; }
    N[n] = -1; D[m + 1][n] = 1;
  }

  void Pivot(int r, int s) {
    for (int i = 0; i < m + 2; i++) if (i != r)
      for (int j = 0; j < n + 2; j++) if (j != s)
        D[i][j] -= D[r][j] * D[i][s] / D[r][s];
    for (int j = 0; j < n + 2; j++) if (j != s) D[r][j] /= D[r][s];
    for (int i = 0; i < m + 2; i++) if (i != r) D[i][s] /= -D[r][s];
    D[r][s] = 1.0 / D[r][s];
    swap(B[r], N[s]);
  }

  bool Simplex(int phase) {
    int x = phase == 1 ? m + 1 : m;
    while (true) {
      int s = -1;
      for (int j = 0; j <= n; j++) {
        if (phase == 2 && N[j] == -1) continue;
        if (s == -1 || D[x][j] < D[x][s] || D[x][j] == D[x][s] && N[j] < N[s]) s = j;
      }
      if (D[x][s] > -EPS) return true;
      int r = -1;
      for (int i = 0; i < m; i++) {
        if (D[i][s] < EPS) continue;
        if (r == -1 || D[i][n + 1] / D[i][s] < D[r][n + 1] / D[r][s] ||
          (D[i][n + 1] / D[i][s]) == (D[r][n + 1] / D[r][s]) && B[i] < B[r]) r = i;
      }
      if (r == -1) return false;
      Pivot(r, s);
    }
  }

  DOUBLE Solve(VD &x) {
    int r = 0;
    for (int i = 1; i < m; i++) if (D[i][n + 1] < D[r][n + 1]) r = i;
    if (D[r][n + 1] < -EPS) {
      Pivot(r, n);
      if (!Simplex(1) || D[m + 1][n + 1] < -EPS) return -numeric_limits<DOUBLE>::infinity();
      for (int i = 0; i < m; i++) if (B[i] == -1) {
        int s = -1;
        for (int j = 0; j <= n; j++)
          if (s == -1 || D[i][j] < D[i][s] || D[i][j] == D[i][s] && N[j] < N[s]) s = j;
        Pivot(i, s);
      }
    }
    if (!Simplex(2)) return numeric_limits<DOUBLE>::infinity();
    x = VD(n);
    for (int i = 0; i < m; i++) if (B[i] < n) x[B[i]] = D[i][n + 1];
    return D[m][n + 1];
  }
};

int n;
vector<int> adj[50];
int ideg[50];
VD on;
VVD equations;
vector<int> sumtime;
int sum;
vector<int> Time, Cost;

void dfs(int u)
{
    on[u]=-1.0;
    sum+=Time[u];
    if(adj[u].empty())
    {
        equations.push_back(on);
        sumtime.push_back(sum);
    }
    else
        for(auto& v: adj[u])
            dfs(v);
    sum-=Time[u];
    on[u]=0.0;
}

#define PROBLEM Farmville
class PROBLEM
{
public:
#define METHOD minTime
    int minTime(vector <string> s, vector <int> time, vector <int> cost, int budget)
    {
        Time=time;
        Cost=cost;
        n=s.size();
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                if(s[i][j]=='1')
                    adj[j].push_back(i), ideg[i]++;
        on.resize(n);
        for(int i=0; i<n; i++) if(ideg[i]==0)
            dfs(i);
        VD constraint;
        for(int i=0; i<n; i++)
            constraint.push_back(-Cost[i]);
        int m=equations.size();
        int lo=0, mid, hi=25*50;
        VD b(m);
        for(int i=0; i<n; i++)
        {
            VD v(n, 0.0);
            v[i]=1.0;
            equations.push_back(v);
            b.push_back(Time[i]);
        }
        while(lo<hi)
        {
            mid=(lo+hi)/2;
            for(int i=0; i<m; i++)
                b[i]=-(sumtime[i]-mid);
            LPSolver slv(equations, b, constraint);
            VD x;
            double ans=-slv.Solve(x);
            if(ans<=budget)
                hi=mid;
            else
                lo=mid+1;
        }
        return lo;
    }
};
Compilation error #stdin compilation error #stdout 0s 0KB
stdin
Standard input is empty
compilation info
/usr/lib/gcc/i586-linux-gnu/5/../../../i386-linux-gnu/crt1.o: In function `_start':
(.text+0x18): undefined reference to `main'
collect2: error: ld returned 1 exit status
stdout
Standard output is empty