Submission #1399394


Source Code Expand

#include <bits/stdc++.h>
#define ADD(a, b) a = (a + (ll)b) % mod
#define MUL(a, b) a = (a * (ll)b) % mod
#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)
#define rep(i, a, b) for(int i = a; i < b; i++)
#define rer(i, a, b) for(int i = a - 1; i >= b; i--)
#define all(a) (a).begin(), (a).end()
#define sec second
#define fst first
#define debug(fmt, ...) Debug(__LINE__, ":", fmt, ##__VA_ARGS__)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef pair<pi, pi> ppi;
typedef vector<ll> vec;

const int MAX_N = 100010;
const double eps = 1e-6;
const ll mod = 1000000007;
const int inf = 1 << 30;

void Debug() {cout << '\n'; }

template<class FIRST, class... REST> 
void Debug(FIRST arg, REST... rest) { cout << arg << " "; Debug(rest...); }

template<class T>
ostream& operator<< (ostream& out, const vector<T>& v) {
	out << "[";
	if(!v.empty()) {
		rep(i, 0, (int)v.size() - 1) out << v[i] << ", ";
		out << v.back();
	}
	out << "]";
  return out;
}

template<class S, class T>
ostream& operator<< (ostream& out, const pair<S, T>& v) {
	out << "(" << v.first << ", " << v.second << ")";
	return out;
}

///g++ -g3 -std=c++0x -DLOCAL -Wall -ftrapv -D_GLIBCXX_DEBUG -Wl,-stack,268435456 -o
///g++ -O2 -std=c++0x -DLOCAL -Wall -Wl,-stack,268435456 -o

///////////////////////////////////////////////////////////////////////

int N, L;
deque<pair<double, int>> que;

void solve() {
	cin >> N >> L;

	double res = 0;
	rep(i, 0, N) {
		double a; int b;
		cin >> a >> b;

		int S = L + b;
		while(!que.empty()) {
			pair<double, int> p = que.front();
			if(S - p.sec <= L) {
				que.front().sec -= S - L;
				res -= que.front().fst * (S - L);
				break;
			}
			else {
				S -= que.front().sec;
				res -= que.front().fst * que.front().sec;
				que.pop_front();
			}
		}

		res += a * b;
		cout << res / L << "\n";

		while(!que.empty() && a < que.back().fst) {
			a = (que.back().fst * que.back().sec + a * b) / (b + que.back().sec);
			b += que.back().sec;
			que.pop_back();
		}
		que.push_back(pair<double, int>(a, b));
	}
}

int main() {
	ios::sync_with_stdio(false);
    cin.tie(0);	
    cout << fixed;
	cout.precision(20);
#ifdef LOCAL
    freopen("in.txt", "rt", stdin);
#endif	
	solve();
#ifdef LOCAL
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
	return 0;
}

Submission Info

Submission Time
Task F - Dam
User omochana2
Language C++14 (GCC 5.4.1)
Score 900
Code Size 2443 Byte
Status AC
Exec Time 1121 ms
Memory 23568 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 900 / 900
Status
AC × 3
AC × 17
Set Name Test Cases
Sample 00-00.txt, 00-01.txt, 00-02.txt
All 00-00.txt, 00-01.txt, 00-02.txt, 01-00.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt
Case Name Status Exec Time Memory
00-00.txt AC 1 ms 256 KB
00-01.txt AC 1 ms 256 KB
00-02.txt AC 1 ms 256 KB
01-00.txt AC 1086 ms 18944 KB
01-01.txt AC 1093 ms 15360 KB
01-02.txt AC 1064 ms 18944 KB
01-03.txt AC 1071 ms 17992 KB
01-04.txt AC 1078 ms 15232 KB
01-05.txt AC 1117 ms 18944 KB
01-06.txt AC 1091 ms 15360 KB
01-07.txt AC 1121 ms 19200 KB
01-08.txt AC 1089 ms 17992 KB
01-09.txt AC 1074 ms 15232 KB
01-10.txt AC 1084 ms 23568 KB
01-11.txt AC 1055 ms 23568 KB
01-12.txt AC 1055 ms 23568 KB
01-13.txt AC 1051 ms 23568 KB