Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- #include <string>
- #include <vector>
- #include <sstream>
- using namespace std;
- int m, n;
- vector<int> seq;
- struct Step {
- int mid;
- int time;
- int minstarttime;
- };
- vector<vector<Step> > workout;
- struct Span {
- int start;
- int len;
- };
- int getEarliest(vector<Span> &mspan, int len, int &before, int &after, int minstart) {
- if(mspan.size() == 0) {
- return minstart; // empty machine
- } else {
- for(int i = 0; i < mspan.size(); i ++) {
- if(i == 0) {
- if(mspan[i].start >= len + minstart) { // slot between 0 and mspan[i].start
- // get the smallest possible start
- after = i;
- return minstart; // fill the earliest slot
- }
- } else {
- int prevend = mspan[i-1].start + mspan[i-1].len;
- int mlen = mspan[i].start - prevend;
- if(mlen >= len && minstart+len <= mspan[i].start) {
- before = i-1;
- after = i;
- return max(minstart, prevend);
- }
- }
- }
- // insert at the back
- before = mspan.size() - 1;
- return max(minstart, mspan.back().start + mspan.back().len);
- }
- }
- int main() {
- ifstream fin("jsp.in");
- // n items, each item m steps
- fin >> m >> n;
- for(int i = 0; i < m*n; i ++) {
- int t;
- fin >> t;
- seq.push_back(t);
- }
- workout = vector<vector<Step> >(n+1, vector<Step>(m+1, Step{}));
- for(int i = 1; i <= n; i ++) {
- for(int j = 1; j <= m; j ++) {
- int t;
- fin >> t;
- workout[i][j].mid = t;
- }
- }
- for(int i = 1; i <= n; i ++) {
- for(int j = 1; j <= m; j ++) {
- int t;
- fin >> t;
- workout[i][j].time = t;
- }
- }
- int total = 0;
- vector<int> currentStep = vector<int>(n+1, 1);
- vector<vector<Span> > mspan = vector<vector<Span> >(m+1, vector<Span>());
- for(int i = 0; i < m * n; i ++) {
- int citem = seq[i];
- int cstep = currentStep[citem];
- Step s = workout[citem][cstep];
- int cmachine = s.mid;
- int citemstart = s.minstarttime;
- int before = -1, after = -1;
- int cstart = getEarliest(mspan[cmachine], s.time, before, after, citemstart);
- if(after == -1) { // insert at the end
- mspan[cmachine].push_back(Span{.start = cstart, .len = s.time});
- } else { // insert at position after
- vector<Span>::iterator it = mspan[cmachine].begin();
- mspan[cmachine].insert(it+after, Span{.start = cstart, .len = s.time});
- }
- currentStep[citem] ++;
- if(currentStep[citem] <= m) {
- workout[citem][currentStep[citem]].minstarttime = cstart + s.time;
- }
- }
- for(int i = 1; i <= m; i ++) {
- if(!mspan[i].size()) {
- continue;
- }
- Span &s = mspan[i].back();
- if(total < s.start + s.len) {
- total = s.start + s.len;
- }
- }
- ofstream fout("jsp.out");
- fout << total << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement