Test #30 was found to be incorrect. It has been removed. The failing solutions have been rejudged.

#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define sz(a) ((int)a.size())
#define re return
#define all(a) a.begin(),a.end()
#define int long long
#define rept(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,a) rept(i,0,a)
#define vi vector<int>
#define pii pair<int,int>
#define F first
#define S second
using namespace std;
const int MOD=1000000007,INF=1000000000000000000;
template<typename T>inline void Mx(T &a,T b){a=max(a,b);}
template<typename T>inline void Mi(T &a,T b){a=min(a,b);}
inline int ad(int &a,int b,int c=MOD){re a=(a+b)%c;}
template<typename T>inline T read(){T a;cin>>a;re a;}
inline bool is_digit(int msk,int d){re (msk>>d)&1;}
const int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
struct thing{int a,b,c,id;}p[100005];
bool operator<(thing a,thing b){
    int p=a.a+b.c+max(a.b+a.c,b.a+b.b);
    int q=b.a+a.c+max(b.b+b.c,a.a+a.b);
    if(p==q)re a.a<b.a;
    re p<q;
}
int n;
void run(){
    cin>>n;
    rep(i,n)cin>>p[i].a>>p[i].b>>p[i].c,p[i].id=i+1;
    sort(p,p+n);
    int a=0,b=0,c=0;
    rep(i,n){
        a=a+p[i].a;
        b=max(a,b)+p[i].b;
        c=max(b,c)+p[i].c;
    }
    cout<<c<<"\n";
    rep(i,n)cout<<p[i].id<<" ";
    cout<<"\n";
}
signed main()
{
//    ios::sync_with_stdio(0);
//    cin.tie(0);cout.tie(0);
//    for(int tc=read<int>();tc;tc--)
        run();
    re 0;
}

This will make your program accepted. I've tried it.

The process to prove it  is both easy and creative.
Sort all the numbers in the following way:

^
|a<c: sort them according to its value of A+B in increasing order
|
|a=c: you may sort them arbitrarily
|
|a>c: sort them according to its value of B+C in decreasing order
|

I made absolute standard algo for
3-machine scheduling with dominated one of machine
and took 1 place in problem rating!
How can it be if so many top programmers presence
in this list.

Also: qsort() from stdlib.h didn't give chance go far then WA12. I used old, kind my qsort and got AC immediately.

Edited by author 03.02.2009 10:03

Is it a knapsack problem?

I can't pass TEST 12 . Why??? Please send me Test 12

Test #18 has numbers greater then 1000000, as mentioned in other thread, so problem's description (or tests) still need to be corrected.

Edited by author 24.03.2007 01:02

what is that test? none of my solutions can pass it. Please give me some hints!!!

When I submit the program with the comparison function shown below, I get WA 27. But if I use a similar comparison function as bruce described in the other topic, i get AC. What's weird is that both result in the same answer (I assert-ed this), but maybe different permutations. So unless my evaluation function (also shown below) is wrong, the judge does not accept all valid permutations.

ll calc() {
    ll ca=0,cb=0,cc=0;
    REP(i,n) { ca+=x[i].a; cb=max(ca,cb)+x[i].b; cc=max(cb,cc)+x[i].c; }
    return cc;
}



typedef struct cmp2 {
    bool operator() (const X &x,const X &y) {
        return min(y.a+y.b,x.b+x.c)>min(x.a+x.b,y.b+y.c);
    }
} cmp2;

Edited by author 19.02.2007 05:37

I carefully wrote my solution to not put any extraneous spaces at the end of the second line and it came back WA #1 every time during the contest. If I now put a space at the end of the line, it comes back as WA #12.