Submission #3977225


Source Code Expand

Copy
#include<algorithm>
#include<complex>
#include<ctype.h>
#include<iomanip>
#include<iostream>
#include<map>
#include<math.h>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<stdio.h>
#include<string>
#include<string>
#include<vector>

using namespace std;
typedef long long ll;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<endl
#define p2(s, t) cout << (s) << " " << (t) << endl
#define pn(s) cout << (#s) << " " << (s) << endl
#define p_yes() p("Yes")
#define p_no() p("No")

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

const ll mod = 1e9 + 7;
const ll inf = 1e18;

struct Info{
    ll weight;
    double percent;
    Info(){}
    Info(ll w, double p){
        weight = w;
        percent = p;
    }
};

ll N, K;
vector<Info> A;
vector<double> scores;

bool makable(double target_percentage){
    
    FOR(i, 0, N){
        auto info = A[i];
        double score = (info.percent - target_percentage) * info.weight * 0.01;
        scores[i] = score;
    }

    sort(ALL(scores), greater<double>());

    double sum = 0;
    FOR(i, 0, K){
        sum += scores[i];
    }

    if(sum >= 0){
        return true;
    }else{
        return false;
    }
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    cin >> N >> K;
    A.reserve(N);
    scores.resize(N);

    FOR(i, 0, N){
        ll w;
        double p;
        cin >> w >> p;
        A.push_back(Info(w, p));
    }

    double OK = 0;
    double NG = 100;

    FOR(i, 0, 1000){
        double half = (OK + NG) / 2.0;
        if(makable(half)){
            OK = half;
        }else{
            NG = half;
        }
    }

    printf("%09f\n", OK);
    
    return 0;
}

Submission Info

Submission Time
Task D - 食塩水
User peroon
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1748 Byte
Status
Exec Time 25 ms
Memory 256 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
× 2
× 22
Set Name Test Cases
Sample s0.txt, s1.txt
All 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, s0.txt, s1.txt
Case Name Status Exec Time Memory
000.txt 24 ms 256 KB
001.txt 3 ms 256 KB
002.txt 25 ms 256 KB
003.txt 3 ms 256 KB
004.txt 25 ms 256 KB
005.txt 23 ms 256 KB
006.txt 24 ms 256 KB
007.txt 18 ms 256 KB
008.txt 24 ms 256 KB
009.txt 3 ms 256 KB
010.txt 25 ms 256 KB
011.txt 8 ms 256 KB
012.txt 25 ms 256 KB
013.txt 8 ms 256 KB
014.txt 24 ms 256 KB
015.txt 16 ms 256 KB
016.txt 25 ms 256 KB
017.txt 12 ms 256 KB
018.txt 23 ms 256 KB
019.txt 14 ms 256 KB
s0.txt 1 ms 256 KB
s1.txt 1 ms 256 KB