結果
| 問題 |
No.453 製薬会社
|
| コンテスト | |
| ユーザー |
 hamray
|
| 提出日時 | 2021-01-27 00:10:50 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 2 ms / 2,000 ms |
| コード長 | 13,101 bytes |
| コンパイル時間 | 2,044 ms |
| コンパイル使用メモリ | 182,992 KB |
| 実行使用メモリ | 6,944 KB |
| 最終ジャッジ日時 | 2024-06-23 22:07:00 |
| 合計ジャッジ時間 | 2,744 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 9 |
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:449:19: warning: narrowing conversion of '(28 * Cc)' from 'int' to 'double' [-Wnarrowing]
449 | double B[]={28*Cc,28*Dd}; // should initialis the b array here
| ~~^~~
main.cpp:449:25: warning: narrowing conversion of '(28 * Dd)' from 'int' to 'double' [-Wnarrowing]
449 | double B[]={28*Cc,28*Dd}; // should initialis the b array here
| ~~^~~
ソースコード
#include <bits/stdc++.h>
//#include <atcoder/all>
//using namespace atcoder;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
using namespace std;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<int, int> pii;
typedef pair<long long, long long> PLL;
typedef pair<int, PII> TIII;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define FOR(i, s, n) for (int i = s; i < (int)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define trav(a, x) for (auto &a : x)
#define all(x) x.begin(), x.end()
#define MOD 1000000007
template<class T1, class T2> inline bool chmax(T1 &a, T2 b) {if (a < b) {a = b; return true;} return false;}
template<class T1, class T2> inline bool chmin(T1 &a, T2 b) {if (a > b) {a = b; return true;} return false;}
const double EPS = 1e-9, PI = acos(-1);
const double pi = 3.141592653589793238462643383279;
//ここから編集
typedef string::const_iterator State;
ll GCD(ll a, ll b){
return (b==0)?a:GCD(b, a%b);
}
ll LCM(ll a, ll b){
return a/GCD(a, b) * b;
}
template< int mod >
struct ModInt {
int x;
ModInt() : x(0) {}
ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}
ModInt &operator+=(const ModInt &p) {
if((x += p.x) >= mod) x -= mod;
return *this;
}
ModInt &operator-=(const ModInt &p) {
if((x += mod - p.x) >= mod) x -= mod;
return *this;
}
ModInt &operator*=(const ModInt &p) {
x = (int) (1LL * x * p.x % mod);
return *this;
}
ModInt &operator/=(const ModInt &p) {
*this *= p.inverse();
return *this;
}
ModInt operator-() const { return ModInt(-x); }
ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }
ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }
ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }
ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }
bool operator==(const ModInt &p) const { return x == p.x; }
bool operator!=(const ModInt &p) const { return x != p.x; }
ModInt inverse() const {
int a = x, b = mod, u = 1, v = 0, t;
while(b > 0) {
t = a / b;
swap(a -= t * b, b);
swap(u -= t * v, v);
}
return ModInt(u);
}
ModInt pow(int64_t n) const {
ModInt ret(1), mul(x);
while(n > 0) {
if(n & 1) ret *= mul;
mul *= mul;
n >>= 1;
}
return ret;
}
friend ostream &operator<<(ostream &os, const ModInt &p) {
return os << p.x;
}
friend istream &operator>>(istream &is, ModInt &a) {
int64_t t;
is >> t;
a = ModInt< mod >(t);
return (is);
}
static int get_mod() { return mod; }
};
using modint = ModInt< 1000000007 >;
template< typename T >
struct Combination {
vector< T > _fact, _rfact, _inv;
Combination(int sz) : _fact(sz + 1), _rfact(sz + 1), _inv(sz + 1) {
_fact[0] = _rfact[sz] = _inv[0] = 1;
for(int i = 1; i <= sz; i++) _fact[i] = _fact[i - 1] * i;
_rfact[sz] /= _fact[sz];
for(int i = sz - 1; i >= 0; i--) _rfact[i] = _rfact[i + 1] * (i + 1);
for(int i = 1; i <= sz; i++) _inv[i] = _rfact[i] * _fact[i - 1];
}
inline T fact(int k) const { return _fact[k]; }
inline T rfact(int k) const { return _rfact[k]; }
inline T inv(int k) const { return _inv[k]; }
T P(int n, int r) const {
if(r < 0 || n < r) return 0;
return fact(n) * rfact(n - r);
}
T C(int p, int q) const {
if(q < 0 || p < q) return 0;
return fact(p) * rfact(q) * rfact(p - q);
}
T H(int n, int r) const {
if(n < 0 || r < 0) return (0);
return r == 0 ? 1 : C(n + r - 1, r);
}
};
class Simplex{
private:
int rows, cols;
//stores coefficients of all the variables
std::vector <std::vector<double> > A;
//stores constants of constraints
std::vector<double> B;
//stores the coefficients of the objective function
std::vector<double> C;
double maximum;
bool isUnbounded;
public:
Simplex(std::vector <std::vector<double> > matrix,std::vector<double> b ,std::vector<double> c){
maximum = 0;
isUnbounded = false;
rows = matrix.size();
cols = matrix[0].size();
A.resize( rows , vector<double>( cols , 0 ) );
B.resize(b.size());
C.resize(c.size());
for(int i= 0;i<rows;i++){ //pass A[][] values to the metrix
for(int j= 0; j< cols;j++ ){
A[i][j] = matrix[i][j];
}
}
for(int i=0; i< c.size() ;i++ ){ //pass c[] values to the B vector
C[i] = c[i] ;
}
for(int i=0; i< b.size();i++ ){ //pass b[] values to the B vector
B[i] = b[i];
}
}
bool simplexAlgorithmCalculataion(){
//check whether the table is optimal,if optimal no need to process further
if(checkOptimality()==true){
return true;
}
//find the column which has the pivot.The least coefficient of the objective function(C array).
int pivotColumn = findPivotColumn();
if(isUnbounded == true){
cout<<"Error unbounded"<<endl;
return true;
}
//find the row with the pivot value.The least value item's row in the B array
int pivotRow = findPivotRow(pivotColumn);
//form the next table according to the pivot value
doPivotting(pivotRow,pivotColumn);
return false;
}
bool checkOptimality(){
//if the table has further negative constraints,then it is not optimal
bool isOptimal = false;
int positveValueCount = 0;
//check if the coefficients of the objective function are negative
for(int i=0; i<C.size();i++){
double value = C[i];
if(value >= 0){
positveValueCount++;
}
}
//if all the constraints are positive now,the table is optimal
if(positveValueCount == C.size()){
isOptimal = true;
}
return isOptimal;
}
void doPivotting(int pivotRow, int pivotColumn){
double pivetValue = A[pivotRow][pivotColumn];//gets the pivot value
double pivotRowVals[cols];//the column with the pivot
double pivotColVals[rows];//the row with the pivot
double rowNew[cols];//the row after processing the pivot value
maximum = maximum - (C[pivotColumn]*(B[pivotRow]/pivetValue)); //set the maximum step by step
//get the row that has the pivot value
for(int i=0;i<cols;i++){
pivotRowVals[i] = A[pivotRow][i];
}
//get the column that has the pivot value
for(int j=0;j<rows;j++){
pivotColVals[j] = A[j][pivotColumn];
}
//set the row values that has the pivot value divided by the pivot value and put into new row
for(int k=0;k<cols;k++){
rowNew[k] = pivotRowVals[k]/pivetValue;
}
B[pivotRow] = B[pivotRow]/pivetValue;
//process the other coefficients in the A array by subtracting
for(int m=0;m<rows;m++){
//ignore the pivot row as we already calculated that
if(m !=pivotRow){
for(int p=0;p<cols;p++){
double multiplyValue = pivotColVals[m];
A[m][p] = A[m][p] - (multiplyValue*rowNew[p]);
//C[p] = C[p] - (multiplyValue*C[pivotRow]);
//B[i] = B[i] - (multiplyValue*B[pivotRow]);
}
}
}
//process the values of the B array
for(int i=0;i<B.size();i++){
if(i != pivotRow){
double multiplyValue = pivotColVals[i];
B[i] = B[i] - (multiplyValue*B[pivotRow]);
}
}
//the least coefficient of the constraints of the objective function
double multiplyValue = C[pivotColumn];
//process the C array
for(int i=0;i<C.size();i++){
C[i] = C[i] - (multiplyValue*rowNew[i]);
}
//replacing the pivot row in the new calculated A array
for(int i=0;i<cols;i++){
A[pivotRow][i] = rowNew[i];
}
}
//print the current A array
void print(){
for(int i=0; i<rows;i++){
for(int j=0;j<cols;j++){
cout<<A[i][j] <<" ";
}
cout<<""<<endl;
}
cout<<""<<endl;
}
//find the least coefficients of constraints in the objective function's position
int findPivotColumn(){
int location = 0;
double minm = C[0];
for(int i=1;i<C.size();i++){
if(C[i]<minm){
minm = C[i];
location = i;
}
}
return location;
}
//find the row with the pivot value.The least value item's row in the B array
int findPivotRow(int pivotColumn){
double positiveValues[rows];
std::vector<double> result(rows,0);
//double result[rows];
int negativeValueCount = 0;
for(int i=0;i<rows;i++){
if(A[i][pivotColumn]>0){
positiveValues[i] = A[i][pivotColumn];
}
else{
positiveValues[i]=0;
negativeValueCount+=1;
}
}
//checking the unbound condition if all the values are negative ones
if(negativeValueCount==rows){
isUnbounded = true;
}
else{
for(int i=0;i<rows;i++){
double value = positiveValues[i];
if(value>0){
result[i] = B[i]/value;
}
else{
result[i] = 0;
}
}
}
//find the minimum's location of the smallest item of the B array
double minimum = 99999999;
int location = 0;
for(int i=0;i<sizeof(result)/sizeof(result[0]);i++){
if(result[i]>0){
if(result[i]<minimum){
minimum = result[i];
location = i;
}
}
}
return location;
}
void CalculateSimplex(){
bool end = false;
while(!end){
bool result = simplexAlgorithmCalculataion();
if(result==true){
end = true;
}
}
for(int i=0;i< A.size(); i++){ //every basic column has the values, get it form B array
int count0 = 0;
int index = 0;
for(int j=0; j< rows; j++){
if(A[j][i]==0.0){
count0 += 1;
}
else if(A[j][i]==1){
index = j;
}
}
}
cout<<maximum<<endl; //print the maximum values
}
};
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
cout << fixed << setprecision(12);
int Cc, Dd; cin >> Cc >> Dd;
int colSizeA=4; //should initialise columns size in A
int rowSizeA = 2; //should initialise columns row in A[][] vector
double C[]= {-1000,-2000,0,0}; //should initialis the c arry here
double B[]={28*Cc,28*Dd}; // should initialis the b array here
double a[2][4] = { //should intialis the A[][] array here
{ 21, 8, 1, 0},
{ 7, 20, 0, 1},
};
std::vector <std::vector<double> > vec2D(rowSizeA, std::vector<double>(colSizeA, 0));
std::vector<double> b(rowSizeA,0);
std::vector<double> c(colSizeA,0);
for(int i=0;i<rowSizeA;i++){ //make a vector from given array
for(int j=0; j<colSizeA;j++){
vec2D[i][j] = a[i][j];
}
}
for(int i=0;i<rowSizeA;i++){
b[i] = B[i];
}
for(int i=0;i<colSizeA;i++){
c[i] = C[i];
}
// hear the make the class parameters with A[m][n] vector b[] vector and c[] vector
Simplex simplex(vec2D,b,c);
simplex.CalculateSimplex();
return 0;
}