結果

問題 No.453 製薬会社
コンテスト
ユーザー mamekin
提出日時 2016-12-12 00:13:02
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 2,278 bytes
コンパイル時間 1,155 ms
コンパイル使用メモリ 110,412 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-29 04:08:32
合計ジャッジ時間 1,963 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
using namespace std;

const double EPS = 1.0e-10;

// 行列の基本変形を行い、行列のランクを返す
int elementaryMatrix(vector<vector<double> >& mat)
{
    const int n = mat.size();
    const int m = mat[0].size();
    int y = 0;
    int x = 0;
    while(y < n && x < m){
        int tmp = y;
        for(int i=y+1; i<n; ++i){
            if(abs(mat[i][x]) > abs(mat[tmp][x]))
                tmp = i;
        }
        if(abs(mat[tmp][x]) > EPS){
            mat[y].swap(mat[tmp]);
            for(int i=y+1; i<n; ++i){
                for(int j=m-1; j>=x; --j){
                    mat[i][j] -= mat[y][j] * (mat[i][x] / mat[y][x]);
                }
            }
            ++ y;
        }
        ++ x;
    }
    mat.resize(y);
    return y;
}

// 連立方程式の解を求める
bool linearSystem(vector<vector<double> >& mat, vector<double>& x)
{
    int n = mat[0].size() - 1;
    if(elementaryMatrix(mat) != n || mat[n-1][n-1] == 0)
        return false;

    x.resize(n);
    for(int i=n-1; i>=0; --i){
        x[i] = mat[i][n];
        for(int j=i+1; j<n; ++j)
            x[i] -= mat[i][j] * x[j];
        x[i] /= mat[i][i];
    }
    return true;
}

const double MATERIAL[2][2] =
{
    { 3.0 / 4.0, 1.0 / 4.0 },
    { 2.0 / 7.0, 5.0 / 7.0 },
};
const int VALUE[2] =
{
    1000,
    2000,
};

int main()
{
    double c, d;
    cin >> c >> d;

    double ans = 0.0;
    for(int i=0; i<2; ++i){
        double x = min(c / MATERIAL[i][0], d / MATERIAL[i][1]);
        ans = max(ans, x * VALUE[i]);
    }

    vector<vector<double> > mat =
    {
        {MATERIAL[0][0], MATERIAL[1][0], c},
        {MATERIAL[0][1], MATERIAL[1][1], d},
    };
    vector<double> x;
    linearSystem(mat, x);
    if(x[0] > 0 && x[1] > 0)
        ans = max(ans, x[0] * VALUE[0] + x[1] * VALUE[1]);

    printf("%.10f\n", ans);

    return 0;
}
0