[Round 1A 2017] Problem B. Ratatouille : https://code.google.com/codejam/contest/5304486/dashboard#s=p1

Ratatouille.cpp

//
//  Created by fpdjsns
//  Copyright © 2019 fpdjsns. All rights reserved.
//
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

// greedy
/*
 * 시간복잡도 : O(max(Q[i] / R[i]) * N)
 * 공간복잡도 : O(NP)
 */
int main() {
	int t;
	cin >> t;
	for (int c = 1; c <= t; c++) {
		int N, P;
		cin >> N >> P;
		
		vector<int> R(N); // R[i] = i번째 재료의 gram
		vector<vector<int>> Q(N, vector<int>(P)); // Q[i][j] = i번째 재료의 j번 패키지 gram

		for (int i = 0; i < N; i++) cin >> R[i];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < P; j++) 
				cin >> Q[i][j];
			sort(Q[i].begin(), Q[i].end()); // 오름차순 정렬
		}

		int cnt = 1; // 재료가 사용되는 수
		int answer = 0;
		vector<int> index(N, 0); //index[i] = i번째 재료에서 현재 탐색하고자 하는 패키지 인덱스
		while (9 * (cnt * R[0]) <= 10 * Q[0][P - 1]) {
			bool isEnd = false;

			// update index array
			for (int i = 0; i < N; i++) {
				// i번째 재료를 cnt개 사용하는데 필요한 재료 인덱스 update
				while (index[i] < P && Q[i][index[i]] * 10 < (cnt * R[i]) * 9) {
					index[i]++;
				}
				// 더이상 사용할 수 있는 i번 재료가 없는 경우
				if (index[i] >= P) {
					isEnd = true; // 종료
					break;
				}
			}

			if (isEnd) break;

			// find can answer
			for (int i = 0; i < N; i++) {
				if ((cnt * R[i] * 9 <= Q[i][index[i]] * 10) && Q[i][index[i]] * 10 <= (cnt * R[i] * 11)) continue;

				// can not make Ratatouille with cnt -> will be cnt++
				isEnd = true;
				break;
			}


			if (isEnd) {
				cnt++;
			}else{
				answer++;

				// use Q[i][index[i]] -> update index array
				for (int i = 0; i < N; i++) index[i]++;
			}
		}

		printf("Case #%d: %d\n", c, answer);
	}
	return 0;
}