AOJ 0530 Pyon-Pyon River Crossing

今日はJOI予選です。5完を目指します
問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0530

解法
動的計画法をつかう
横の列の個数分の配列をとるとTLEしそう。
そこで、一つの行には石がたかだか10個しかないという制約を利用するとはやくなる

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;
const ll INF = 100000000000000;
ll dan(P p1, P p2){ return (p1.second + p2.second) * abs(p2.first - p1.first); }
int main(){
	ll n, m;
	while(true){
		scanf("%lld %lld", &n, &m);
		if(n == 0) break;
		vector<P> a[n + 1];
		ll dp[n + 1][10][m + 1];
		//初期化
		for(int i = 0; i <= n; i++)
			for(int j = 0; j < 10; j++)
				for(int k = 0; k < m + 2; k++)
					dp[i][j][k] = (i==0 || i==1)?0:INF;
		for(int i = 1; i <= n; i++){
			int ki;
			scanf("%d", &ki);
			for(int j = 0; j < ki; j++){
				ll x, d;
				scanf("%lld %lld", &x, &d);
				a[i].push_back(P(x, d));
			}
		}
		for(int i = 2; i <= n; i++){
			for(int j = 0; j < a[i].size(); j++){
				for(int k = m; k >= 0; k--){
					ll t = INF;
					for(int l = 0; l < a[i-1].size(); l++)
						t = min(t, dan(a[i-1][l], a[i][j]) + dp[i-1][l][k]);
					if(k < m){
						if(i == 2)t = 0;
						for(int l = 0; l < a[i-2].size(); l++){
							t = min(t, dan(a[i-2][l], a[i][j]) + dp[i-2][l][k + 1]);
						}
						t = min(t, dp[i][j][k + 1]);
					}
					dp[i][j][k] = t;
				}
			}
		}
		/*
		for(int i = 0; i <= n; i++){
			printf("%d| ", i);
			for(int j = 0; j < a[i].size(); j++){
				printf(" %lld", dp[i][j][1]);
			}
			puts("");
		}
		*/
		ll ans = INF;
		for(int j = 0; j < a[n].size(); j++)
			ans = min(ans, dp[n][j][0]);
		if(m >= 1)
		for(int j = 0; j < a[n-1].size(); j++)
			ans = min(ans, dp[n-1][j][1]);
		printf("%lld\n", ans);
	}
	return 0;
}