제출 #1297971

#제출 시각아이디문제언어결과실행 시간메모리
1297971rubypowerscrollJob Scheduling (CEOI12_jobs)C++17
100 / 100
331 ms26616 KiB
#include <bits/stdc++.h> using namespace std; int main() { int n,d,m; cin>>n>>d>>m; vector<array<int, 2>> arr(m); int i = 0; for(auto &[x, v] : arr) { cin>>x; v=++i; } sort(arr.begin(),arr.end()); int lo = 0; int hi = m + 1; vector<vector<int>> answer; while (lo < hi) { int mid = lo + (hi - lo) / 2; int job = 0; bool valid = true; vector<vector<int>> schedule(n + 1); for (int day = 1; day <= n; ++day) { int tasks = 0; while (job < m && arr[job][0] <= day && tasks < mid) { if (day > arr[job][0] + d) { valid = false; break; } schedule[day].push_back(arr[job][1]); ++tasks; ++job; } if (!valid) { break; } } if (valid) { hi = mid; swap(schedule, answer); } else { lo = mid + 1; } } cout << lo << "\n"; for (int day = 1; day <= n; ++day) { auto const &row = answer[day]; auto first = begin(row); auto last = end(row); for (; first != last; ++first) cout << *first << " "; cout << "0\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...