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 |
|
|
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 |