/* nov2014 : oscar+xtof+yasmina greedy triangle scheduling
g++ -std=gnu++0x greedy.cpp -o greedy
*/

#include <iostream>
#include <algorithm>
#include <sstream>

using namespace std;

typedef double SIZE;

const int MAX = 1000;

SIZE *ptab;
bool decreasing(int a, int b) {
    return ptab[a]>ptab[b];
}

/**
in:
  n = number of jobs, all arrays are of length n
  p = processing times
out:
  o = order, o[r]=job with rank r, 0-based
  s = starting time of each job by rank, s[n] = makespan
  w = makespan defining weight in {0,1,2}
  returns makespan
complexity:
  O(n^3)
*/
SIZE greedy(int n, SIZE p[], int o[], SIZE s[], int w[]) {
    int j[MAX];
    for (int i=0; i<n; i++)           // job indexes
        j[i] = i;
    ptab = p;
    sort(j, j+n, decreasing);         // process jobs in decreasing order
    SIZE makespan = 0;
    s[0] = 0;                         // initialize makespan
    for (int a=0; a<n; a++) {
        SIZE largest = 0 ;            // largest gap
        int pos = 0;                  // index of largest gap
        int i = j[a];                 // a-th largest job
        for (int b=1; b<=a; b++)       // find largest gap job for i
            if (s[b]-s[b-1] > largest) {
                pos = b;
                largest = s[b]-s[b-1];
            }
        for (int c=a; c>pos; c--)     // insert at position pos
            o[c] = o[c-1];            // shift rank of subsequent jobs
        o[pos] = i;
        for (int c=pos; c<=a; c++) {  // shift starting time of jobs
            SIZE t = 0;
            for (int d=0; d<c; d++)
                t = max(t, s[d] + min(p[o[d]], p[o[c]]));
            s[c] = t;                 // set new starting time
            makespan = max(makespan, s[c]+p[o[c]]);
        }
        s[a+1] = makespan;
    }
    for (int j=0; j<n; j++)
        w[j] = 0;
    return makespan;
}

int D = 5;
const char *color[] = {"white", "yellow", "orange"};

int main(int argc, char *argv[]) {
    int o[MAX], w[MAX];
    SIZE p[MAX], s[MAX];
    if (argc==3 && argv[1][0]=='-') {
        string instance(argv[2]);
        int n = 0;
        {
        stringstream in(instance, ios_base::in);
        SIZE pi;
        while (in>>pi)
            n++;
        }
        SIZE pmax = 0;
        stringstream in(instance, ios_base::in);
        for(int i=0; i<n; i++) {
            in >> p[i];
            pmax = max(pmax, p[i]);
//           cerr << "pi="<< p[i] << endl;
        }
        SIZE width, makespan = greedy(n, p, o, s, w);
        if (makespan < 40)
            D = 15;
        width = max(makespan, 20.) * D;
        SIZE bot = pmax * D;
        if (argv[1][1]=='i') {
            cout << "<?xml version=\"1.0\" standalone=\"no\"?>" << endl
                 << "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.0//EN\" \"http://www.w3.org/TR/2001/REC-SVG-20010904/DTD/svg10.dtd\">" << endl;
            cout << "<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" "
                    "font-family=\"sans-serif\" font-size=\"10pt\" width=\"" << width << "\" height=\"" << bot + 20 << "\" >" << endl;
            // cout << " <line x1=\"" << left << "," << bot << " " << left << "," << top << " " << right << "," << top
            //          << " " << left  << "," << bot << "\" style=\"fill:" << color[w[a]] << ";stroke:black;stroke-width:1\" /> "<< endl;
            for (int a=0; a<n; a++) {
                SIZE si = s[a];
                SIZE pi = p[o[a]];
                SIZE top = bot - pi*D;
                SIZE left =  si*D;
                SIZE right = (si+pi)*D;
                cout << " <polygon points=\"" << left << "," << bot << " " << left << "," << top << " " << right << "," << top
                     << " " << left  << "," << bot << "\" style=\"fill:" << color[w[a]] << ";stroke:black;stroke-width:1\" /> "<< endl;
                if (pi>3)
                    cout << "<text x=\"" << left + 2 << "\" y=\"" << top + 13 << "\">" << pi << "</text>" << endl;
            }
            cout << "<text x=\"0\" y=\"" << bot + 13 << "\">makespan = "<< makespan << "</text>" << endl;
            cout << "</svg>"<< endl;
        }
        else {
            for (int a=0; a<n; a++)
                cout << "\\job{" << s[a] << "}{" << p[o[a]] << "}{" << w[a]*10 << "}\n";
        }
        return 0;
    }
    int n = argc-1;
    for (int i=0; i<n; i++)
        p[i] = atof(argv[i+1]);
    cout << "makespan=" << greedy(n, p, o, s, w) << endl;
    for (int i=0; i<n; i++)
        cout << "job " << o[i] << " at " << s[i] << endl;
}