結果

問題 No.453 製薬会社
ユーザー simezi_tansimezi_tan
提出日時 2016-12-04 00:09:05
言語 C++11
(gcc 11.4.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,143 bytes
コンパイル時間 1,083 ms
コンパイル使用メモリ 160,872 KB
実行使用メモリ 17,224 KB
最終ジャッジ日時 2024-11-27 14:42:51
合計ジャッジ時間 43,930 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 TLE -
testcase_02 TLE -
testcase_03 TLE -
testcase_04 TLE -
testcase_05 TLE -
testcase_06 TLE -
testcase_07 TLE -
testcase_08 TLE -
testcase_09 TLE -
testcase_10 TLE -
testcase_11 TLE -
testcase_12 TLE -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int doit(int)’:
main.cpp:72:1: warning: no return statement in function returning non-void [-Wreturn-type]
   72 | }
      | ^

ソースコード

diff # 

#include<bits/stdc++.h>

using namespace std;

#define ALL(c) c.begin(), c.end()
#define FOR(i,c) for(typeof(c.begin())i=c.begin();i!=c.end();++i)
#define REP(i,n) for(int i=0;i<n;++i)
#define fst first
#define snd second

const double EPS = 1e-6, INF = 1./0.;

double simplexMethodPD(double c[], int n, double b[], int m, double A[]) {
  double T[m+1][n+m+1];
  memset(T, 0, sizeof(T));
  REP(j, m) {
    REP(i, n) T[j][i] = A[j*n+i];
    T[j][n+j] = 1;
    T[j][n+m] = b[j];
  }
  REP(i, n) T[m][i] = c[i];
  while (1) { 
    int p = 0, q = 0;
    REP(i, n+m) if (T[m][i] <= T[m][p]) p = i;
    REP(j, m) if (T[j][n+m] <= T[q][n+m]) q = j;
    double t = min(T[m][p], T[q][n+m]);
    if (t >= -EPS) return -T[m][n+m]; // optimal

    if (t < T[q][n+m]) { // tight on c -> primal update
      REP(j, m) if (T[j][p] >= EPS) 
        if (T[j][p]*(T[q][n+m]-t) >= T[q][p]*(T[j][n+m]-t)) q = j;
      if (T[q][p] <= EPS) return INF; // primal infeasible
    } else { // tight on b -> dual update
      REP(i, n+m+1) T[q][i] *= -1;
      REP(i, n+m) if (T[q][i] >= EPS) 
        if (T[q][i]*(T[m][p]-t) >= T[q][p]*(T[m][i]-t)) p = i;
      if (T[q][p] <= EPS) return -INF; // dual infeasible
    }
    REP(i, m+n+1) if (i != p) T[q][i] /= T[q][p]; T[q][p] = 1; // pivot(q,p)
    REP(j, m+1) if (j != q) {
      double alpha = T[j][p];
      REP(i, n+m+1) T[j][i] -= T[q][i] * alpha;
    }
  }
}

#include <ctime>
int doit(int seed) {
  srand(seed);

  int n = 2, m = 2;
  double c[n];
  double A[m*n];
  double b[m];
  c[0] = -1000; c[1] = -2000;
  REP(i, m) cin >> b[i];
  A[0] = 3/4.; A[2] = 1/4.; A[1] = 2/7.; A[3] = 5/7.;
/*
  cout << "c = [";
  REP(i,n) cout << c[i] << (i == n-1 ? "];" : ","); cout << endl;
  cout << "b = [";
  REP(i,m) cout << b[i] << (i == m-1 ? "];" : ";"); cout << endl;
  cout << "A = [";
  REP(j, m) {
    REP(i, n) cout << A[j*n+i] << (i == n-1 ? j == m-1 ? "];" : ";" : ",");
  }
  cout << endl;
  cout << "[sol,opt] = linprog(c,[A;-eye(size(c,2))],[b;zeros(size(c,2),1)])" << endl;
  cout << endl;
*/
	cout << fixed << setprecision(20) << -simplexMethodPD(c, n, b, m, A) << endl;
}

int main() { doit( time(0) ); }
0