//@EXPECTED_RESULTS@: TIME_LIMIT_EXCEEDED, WRONG_ANSWER #include #include #include #include // TLE and WA: doesn't sort and then overflows a calculation as maxv can become somewhat large and then * y is too big. int main(){ int n, m; std::cin >> n >> m; std::vector xs; int x; for (int i = 0; i < n; i++) { std::cin >> x; xs.push_back(x); } long long t = 0; // first do f = M for (int i = 0; i < n; i++) { x = xs[i]; t += (m * x) / 1000 + ((m * x) % 1000 == 0 ? 0 : 1); } float optt = (float)t / m; // Now all interesting points for (int i = 0; i < n; i++) { x = xs[i]; int maxv = (m * x) / 1000; for (int k = 1; k <= maxv; k++) { //DO NOT enumerate in sorted order -> TLE t = 0; for (int j = 0; j < n; j++) { int y = xs[j]; // k * y overflows if ((k * y) % x == 0) t += (k * y) / x; else t += 1 + (k * y) / x; } std::cout << t << ' ' << x << ' ' << k << std::endl; float curt = ((float)t * x) / (1000.0f * k); if (curt < optt) optt = curt; } } std::cout << std::setprecision(10) << optt << std::endl; }