Am reusit sa implementez ideea din articolul cu solutii si am luat 100 de puncte, insa nu imi dau seama cum s-a ajuns la aceasta solutie.
Doreste cineva sa ma ajute?

Nu ai voie sa folosesti decat atacurile pentru care k = 0.

Multe multumiri 

Aceasta este functia recurenta la care m-am gandit pentru a rezolva problema:

Cod:

void rec(int x,int k1,int k2,int k3,int ts){
    if(!x){
        int ax=k1*a1+k2*a2+k3*a3;
        if(mn==ts){
            qti=min(qti,ax);
        }else if(mn>ts){
            mn=ts;
            qti=ax;
        }
        return;
    }

    rec(max(0,x-a1),t1,max(k2-1,0),max(k3-1,0),ts+1+k1);
    rec(max(0,x-a2),max(k1-1,0),t2,max(k3-1,0),ts+1+k2);
    rec(max(0,x-a3),max(k1-1,0),max(k2-1,0),t3,ts+1+k3);
    return;
}

Iar acesta este apelul ei

Cod:

rec(x,0,0,0,0)

.
qti si mn sunt variabile globale care retin timpul minim si suma:a1*k1+a2*k2+a3*k3.

Stiu ca aceasta abordare nu se incadreaza in limitele de timp si nici nu urmaresc asta. Ma intereseaza sa aflu unde am gresit, la formula recurenta, de nu imi este acceptat pe testele pe care imi intra in limita timp.

Multumesc mult pentru ajutor, oricui se indura!

Am rezolvat cu programare dinamica si am obtinut 90p. Am rezolvat cu grafuri si am obtinut 80p. Am citit in indicatiile de rezolvare ca este necesara folosirea unor "tehnici de alocare si optimizari legate de parcurgerea in latime a grafului" si nu reusesc sa imi dau seama cam care ar fi acele tehnici. Putin ajutor daca se poate, va rog!

Nu mai folosi variabile globale, daca nu stii cum sa le administrezi. Variabila "i" va fi folosita si in functia main si in functia dfs.
Pentru testul 3 0 programul tau da 1 cand ar trebui sa dea 3

Cine participa?

EDIT: Am depasit recent ratingul de 1700(parca atat trebuia pt div 1), stie cineva daca pot participa la asta?

Vreau si eu o parere despre solutia mea:
M-am gandit sa aplic o strategie greedy; la fiecare pas (adica la fiecare poza facuta), incerc sa fac in asa fel incat sa se vada cat mai multe clase (care n-au aparut si in alte poze), in felul urmator: la inceput sortez elevii din fiecare clasa dupa inaltimea lor si apoi incerc sa sortez clasele in asa fel incat daca clasa i poate fi asezata inaintea clasei j la poza astfel incat sa se vada toti elevii din ambele clase, clasa i va fi pe o pozitie inaintea clasei j in sirul sortat al claselor. Acum incerc sa iau un numar maxim de clase astfel incat sa fie vizibile toate la poza; pentru asta voi face un subsir crescator maximal in K dimensiuni. Dupa ce am gasit valoarea Max = lungimea maxima a unui subsir crescator, marchez toate clasele care au format acest subsir ca si folosite: used[clasa] = true si apoi trec la pasul urmator (urmatoarea poza), unde voi forma din nou un subsir maximal crescator, avand grija sa nu folosesc decat clasele unde used[clasa] = false. Algoritmul se repeta pana cand used[j] = true, pentu orice 1 <= j <= N. Complexitatea totala e Nr_pasi*N*logN = N^2*logN.
Eu am gresit implenetarea in timpul concursului, dar nu gasesc niciun contraexemplu.

Criteriul dupa care sortezi clasele nu este complet, deoarece nu ai o metoda sigura de a le ordona in orice caz, dar sa zicem ca le ordonezi lexicografic iar pentru urmatorul test:

n=5,k=4
1 1 4 9
1 3 8 10
5 6 9 9
6 7 9 11
6 8 9 10

Sunt 3 subsiruri formate din:
1 si 5
2 si 4
3

In functie de cum faci dinamica tie iti pot iesi 4 subsiruri:
1 si 4
2
3
5

Acum, daca tot am comentat aici, as vrea o parere despre ideea mea:
Am sortat fiecare clasa dupa inaltime iar dupa aceea am sortat clasele lexicografic.
Am construit un graf orientat ,arcul de la x la y reprezentand faptul ca sirul y poate sta in spatele sirului x.
Pentru fiecare componenta slab conexa a grafului am facut o sortare topologica iar dupa fiecare sortare adunam la rezultat numarul de noduri de pe nivelul cu cele mai multe noduri a componentei slab conexe.

La aceasta problema http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=82 pe testele 8-12 primesc WA.
Am descaracat fisierul "in" si "ok" pentru testul 8, de pe site si am rulat pe datele de intrare din "in". Am comparat raspunsul dat de sursa mea cu cel din "ok"(d.p.d.v lexicografic) si am constatat ca sunt la fel.

Folosesc Code::Blocks 12.11 si compilerul GNU GCC.
Mentionez ca am rulat de mai multe ori, folosind standardele c++98,c++0x si c++11.
Am mai rulat si in Microsoft Visual Studio 2010.
Toate au avut acelasi rezultat.

Imi poate da cineva indicatii in legatura cu ce as putea face gresit sau cum se comporta evaluatorul de pe .campion?

Sursa mea:

Cod:

#include <fstream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cctype>
#include <cassert>

using namespace std;

ifstream f("dezbateri.in");
ofstream g("dezbateri.out");

int main()
{
    vector<int> v[1001];
    int gr[1001]={};

    int n,m;

    f>>n>>m;
    f.ignore();

    for(int i=1;i<=m;i++){
        string a;
        getline(f,a);

        int x[3]={};
        unsigned j=0;

        for(int l=0;l<3;l++){
            while(j<a.size()&&isdigit(a[j])){
                x[l]=x[l]*10+a[j]-'0';
                j++;
            }
            j++;
        }

        j=0;
        while(isdigit(a[j]))
            j++;

        if(a[j]==','){
            v[x[0]].push_back(x[2]);
            v[x[1]].push_back(x[2]);
            gr[x[2]]+=2;
        }
        else{
            v[x[0]].push_back(x[1]);
            v[x[0]].push_back(x[2]);
            gr[x[1]]++;
            gr[x[2]]++;
        }
    }

    vector<int> sl[1001];
    queue<int> q;

    for(int i=1;i<=n;i++)
        if(!gr[i]){
            sl[0].push_back(i);
            q.push(i);
        }

    int nr=0;
    queue<int> ax,ax1;

    while(!q.empty()){
        nr++;
        while(!q.empty()){
            int i=q.front();
            q.pop();

            for(unsigned j=0;j<v[i].size();j++){
                gr[v[i][j]]--;
                if(!gr[v[i][j]]){
                    sl[nr].push_back(v[i][j]);
                    ax.push(v[i][j]);
                }
                if(gr[v[i][j]]==-1){
                    g<<0;
                    return 0;
                }
            }

        }
        q=ax;
        ax=ax1;
    }

    for(int i=1;i<=n;i++)
        if(gr[i]){
            g<<0;
            return 0;
        }

    for(int i=1000;i>=0;i--)
        if(sl[i].size()){
            sort(sl[i].begin(),sl[i].end());
            for(unsigned j=0;j<sl[i].size();j++){
                g<<sl[i][j];
                if(j!=sl[i].size()-1||i!=0)
                    g<<" ";
            }
        }
    g<<'\n';

    return 0;
}

Imi da 96... WA la testu 5, poate sa imi dea cineva vreun caz particular care sa ma ajute sa imi observ greseala?