Submission #2531763

---

Source Code Expand

#include<iostream>
#include<string>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#include<functional>
#include<iomanip>
#include<queue>
#include<cassert>
#include<tuple>
#include<set>
#include<map>
#include<list>
#include<bitset>

#define PB push_back
#define ALL(a)  (a).begin(),(a).end()
#define DWN(a)  (a).begin(),(a).end(), greater<int>()
#define rep(i, m) for (int i = 0; i < m; i++)
#define REP(i, n, m) for (int i = n; i < m; i++)

#define mod 1000000007

using namespace std;

typedef long long ll;
typedef pair<int, int> P;

const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };
const int INF = (int)1e9;

int main() {
	int n;
	cin >> n;
	int t[110];
	double v[110];
	rep(i, n) {
		cin >> t[i] >> v[i];
		t[i] *= 2;
	}
	double max_v[40010];
	fill(max_v, max_v + 40010, INF);
	int cur = 0;
	rep(i, n) {
		REP(j, cur, cur + t[i] + 1) {
			max_v[j] = min(max_v[j], v[i]);
		}
		cur += t[i];
	}
	max_v[0] = 0, max_v[cur] = 0;
	for (int i = 0; i < cur - 1; i++) {
		max_v[i + 1] = min(max_v[i + 1], max_v[i] + 0.5);
	}
	for (int i = cur - 1; i >= 0; i--) {
		max_v[i] = min(max_v[i], max_v[i + 1] + 0.5);
	}
	double ans = 0.0;
	rep(i, cur) {
		ans += max_v[i] + max_v[i + 1];
	}
	cout << ans * 0.25 << endl;
	return 0;
}

Submission Info

Judge Result