閘門式運河: 上下に動く水面

F問題。
C問題とD問題はほかの二人が頑張ってるのでE問題を読んでみる。…無理ぽ。
次にF問題を読む。シミュレーション…だよね？問題にもシミュレーションって書いてあるし。
考えることないような。。
えーと、priority_queueで動かしていけばいいのかな。いや、めんどくさすぎるー！間に合う気がしない！
とか言ってる間にCとDが解けてコーディング開始。
位置の配列用意して、キューにイベント入れていって、んで、えーっと。…あ、無理があるわ。
まあなんか、あとの二人がE問題頑張ってるのでがんばれーと思いつつ閘門の動きを考える。
あれ、よく考えたら1kmごとに到達時間考えればいいのかな…？っていうか先頭から順番に動かせばいいじゃないか。
適当に組んでみる。よくわからんけど違う。印刷して確認する。ああ、明らかにおかしい。
修正。なんか計算が足りてない。適当に2倍。とりあえずサンプル通ってるっぽい！
えーと、どうやって桁数変えるの？桁数変える。うん、合ってると思う！
データDLして実行。segmentation fault。適当に2000だったのを3000に書き換え。実行してとりあえず提出。通った！！

…という経緯でできたソースがこれです。時間かかったわりに、こんだけ？って感じではあるなあ。。

#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <functional>
#include <numeric>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
using namespace std;
typedef long long ll;
#define fs first
#define sc second

int main() {
	for (;;) {
		int N, M, K;
		cin >> N >> M >> K;
		if (!N&&!M&&!K) break;
		vector<int> X(N), L(N), F(N), D(N), UD(N), V(M);
		for (int i = 0; i < N; ++ i) cin >> X[i] >> L[i] >> F[i] >> D[i] >> UD[i];
		for (int i = 0; i < M; ++ i) cin >> V[i];
		
		double kstart[3000], kt1[3000], kt2[3000];
		for (int i = 0; i < 3000; ++ i) kstart[i] = -1;
		for (int i = 0; i < N; ++ i) {
			int x = X[i] + M;
			if (UD[i] == 0) {
				kstart[x] = 0;
				kt1[x] = (double)L[i]/F[i];
				kt2[x] = (double)L[i]/D[i];
			} else {
				kstart[x] = (double)L[i]/F[i];
				kt1[x] = (double)L[i]/D[i];
				kt2[x] = (double)L[i]/F[i];
			}
		}
		
		double times[3000][100];
		for (int s = 0; s < M; ++ s) {
			double t = 0;
			for (int pos = M-s; pos <= M+K*2; ++ pos) {
				if (s > 0) t = max(t, times[pos+1][s-1]);
				times[pos][s] = t;
				if (kstart[pos] >= 0) {
					t = max(t, kstart[pos]);
					t += kt1[pos];
					kstart[pos] = t + kt2[pos];
				}
				t += 1.0/V[s];
			}
		}
		cout << setiosflags(ios::fixed) << setprecision(10) << times[K+M][M-1] << endl;
	}
}

この問題解いたのは3チームだけだったらしい。E問題難しそうだったから他のチームもこれ解いてるとばかり。。
とりあえず、間に合ってとても嬉しかった。
そういえば閘門ってカンモンだとばかり思ってそう言ってたけどコウモンだったらしい。