#2325302

Solution for 0530: Pyon-Pyon River Crossing by olphe

Source Code Status Test Cases
    Policy: public     Reviewed: 5    
00.01 sec    4224 KB    98 lines     2401 bytes    2017-05-19 05:38
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "math.h"
#include "utility"
#include "string"
#include "map"
#include "unordered_map"
#include "iomanip"
#include "random"

using namespace std;
const long long int MOD = 1000000007;

int N,M;
list<long long int>ans;

int main() {
	ios::sync_with_stdio(false);
	cin >> N >> M;
	vector<vector<int>>a(2, vector <int>(4));
	while (N) {
		long long int dp[152][100][10];
		vector<vector<int>>stone(N + 1);
		vector<int>have(N + 2);
		for (int i = 1; i <= N; i++) {
			int a;
			cin >> a;
			have[i] = a;
			for (int j = 0; j < a; j++) {
				int b, c;
				cin >> b >> c;
				stone[i].push_back(b);
				stone[i].push_back(c);
			}
			//cout << "hijiki";
		}
		for (int i = 1; i <= N; i++) {
			for (int j = 0; j <= M; j++) {
				for (int k = 0; k < 10; k++)dp[i][j][k] = INT_MAX;
			}
		}
		//cout << "hijiki";
		for (int i = 0; i < have[1]; i++) {
			dp[1][0][i] = 0;
		}
		if (M) {
			for (int i = 0; i < have[2]; i++) {
				dp[2][1][i] = 0;
			}
		}
	//	cout << "hijiki";
		for (int i = 1; i < N; i++) {
			for (int j = 0; j <= M; j++) {
				for (int k = 0; k < have[i]; k++) {
					for (int l = 0; l < have[i + 1]; l++) {
						if(j)dp[i + 1][j][l] = min(dp[i + 1][j][l], dp[i + 1][j][l]);
						dp[i + 1][j][l] = min(dp[i + 1][j][l], dp[i][j][k] + (stone[i][k * 2 + 1] + stone[i + 1][l * 2 + 1])*(abs(stone[i][k * 2] - stone[i + 1][l * 2])));
					}
					if (j != M) {
						for (int l = 0; l < have[i + 2]; l++) {
							dp[i + 2][j + 1][l] = min(dp[i + 2][j][l], dp[i + 2][j + 1][l]);
							dp[i + 2][j + 1][l] = min(dp[i + 2][j + 1][l], dp[i][j][k] + (stone[i][k * 2 + 1] + stone[i + 2][l * 2 + 1])*(abs(stone[i][k * 2] - stone[i + 2][l * 2])));
						}
					}
				}
			}
		}
		long long int box = INT_MAX;
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < have[N - 1]; j++) {
				box = min(box, dp[N - 1][i][j]);
			}
		}
		for (int i = 0; i <= M; i++) {
			for (int j = 0; j < have[N]; j++) {
				box = min(box, dp[N][i][j]);
			}
		}
		//for (int i = 1; i <= N; i++) {
		//	for (int j = 0; j <= M; j++) {
		//		for (int k = 0; k < have[i]; k++) {
		//			//cout << i << " " << j << " " << k << " " << dp[i][j][k] << endl;
		//		}
		//	}
		//}
		ans.push_back(box);
		cin >> N >> M;
	}
	for (auto i : ans)cout << i << endl;
	return 0;
}

Compile Error Logs:
You are not authorized to see the message.

Status
Judge: 1/1 C++14 CPU: 00.01 sec Memory: 4224 KB Length: 2401 B 2017-05-19 05:38 2017-05-19 05:38
Results for testcases
Case # Verdict CPU Time Memory In Out Case Name
Case #1: : Accepted 00.01 sec 4224 KB
< prev | / | next >  
 
Judge Input #  ( | ) Judge Output #  ( | )


Comments
 
 Under Construction.
 
Categories
 
 
Free Tags