AM 70 pct cu 1 Memory limit exceeded  si 2 TLE
Am facut un cuplaj 
Exista ceva mai optim pentru 100 pct?>
Multumesc Anticipat!!!

Tot nu e bine! Schimba idea !
uite un test pe care pica sursa ta :
7
2 10
1 8
5 3
1 1
9 8
4 3
6 10
Out(corect) : 443

eu nu stiu cum ti-a dat 443
care sunt costurile pt fiecare proces?

   problema asta ma omoara  .
Am calculat si liniar rezultatul dar tot degeaba
Sortarea pe care o fac e corecta (am verificat pe cateva exemple si imi da bine)
Chiar nu stiu ce sa-i mai fac!!!!

  iau 95 pct cu 1 TLE.am parasat citirea + am folosit bool la matrice.ce as mai putea reduce?

 :-kam facut un cuplaj si iau 0 pct cu sursa de 1,24 kb.
Se foloseste o formula ceva,deoarece observ ca sunt surse de  0,25 kb care au 100pct
Multumesc Anticipat!!!!

Care e deci smenu la testul 5?

Daca x<=m aplici formula (daca ai luat 90 cred ca e buna ) si daca x>m raspunsul este 0 deoarece x/m >1  si din formula ta o sa-ti rezulte probabilitate negativa ceea ce este inposibil

Am trimis sursa cu 90 pct cu incorect pe testul 5.Vreo idee ceva?
Am folosit si double si long double ,dar tot 90 pct
Multumsc Anticipat!!!

Am luat 100 pana la urma

Am trimis sursa cu 90 pct cu incorect pe testul 5.Vreo idee ceva?
Am folosit si double si long double ,dar tot 90 pct
Multumsc Anticipat!!!

  am luat 100. de 2 ore tot incercam sa vad dc iau TLE ,dau eu trimiteam alta sursa .

N-ai facut ce am zis eu.

Cod:

int pairup(int start)
{
	if(uz[start])
		return 0;
	uz[start]=1;
	for(IT I=G[start].begin();I!=G[start].end();++I)
			if(!dr[*I]  )
			{
				dr[*I]=start;
				st[start]=*I;
				
				return 1;
			}
	for(IT I=G[start].begin();I!=G[start].end();++I)
				if( pairup(dr[*I] ) )
				{
					dr[*I]=start;
					st[start]=*I;
					return 1;
				}
				
			return 0;
}

nu asa?

Desparte acel for din functia pairup() astfel incat prima data verifici daca il poti cupla simplu cu un vecin si a doua oara daca nu cumva poti recupla nodurile si apoi sa-l cuplezi cu vecinul. Deci sa faci doua for-uri separate pentru fiecare conditie.

am incercat dar tot 60 iau

  am reusit sa iau 60 pct:AM  8 TLE.folosesc Hopcroft Karp .ce as mai putea face sa reduc timpul?

Multumesc Anticipat!!!

Da, trebuie. Gandeste-te ca numarul ala are 10 000 de cifre iar long long poate retine un numar de maxim 18 cifre(aproximativ).

deci p are maxim 10000 cifre
atunci cand calculez termenii si raspund la intrebari in O(1) cum as putea retine eu atatea pozitii? ?

Salutare
urmatoarea restricite: 0 ≤ Pi < 10^10000 am mai vazut-o in cateva probleme ....trebuie sa folosesc numere mari? ma gandesc ca 10 ^ 10000 e cam mare .
Multumesc anticipat!!!

Hmm...inseamna ca algoritmul meu e retardat...
Am facut o dinamica de precalculare de 4000 x N (de sus in jos), apoi raspund pe query in O(1). Not sure ce e gresit.

explica cum ai facut dinamica... :Dai verificat daca poti sari pe a 2 scandura?

Am facut sume partiale si am luat 100

Salajan Razvan: mersi pt sugestie

Salutare.Am folosit la problema asta :
sortarea cu sort din STL + cautarea pozitiei cu upper_bound.
iau 50 pct cu TLE
Nu stiu ce as mai putea reduce...
Vreo sugestie ceva?
Multumesc Anticipat!!!

 :Dsalutare.sunt nou in programarea dinamica
In legatura cu problema aceasta.Mi-am dat seama de recurenta ,dar cu ce ar trebui sa initializez matricea la inceput:? adica pt scandurile de tip 0,1,3 sa pun 1?
intreb asta deoarece daca nu pun nimic in matrice la inceput ,dupa ce fac dinamica matricea are doar 0 in ea(si e normal neavand nici o valoare de inceput);
Multumesc Anticipat!!!

Eu n-am parsat citirea dar ca sa sar de la 90 la 100 a fost nevoie sa fac coada "de mana".

am facut coada de mana ....tot 60 pct

Incearca sa parsezi citirea. Eu doar asa am reusit sa iau 100, si peste cate surse de 100 p m-am uitat, toti au parsat citirea. Bafta!

care este faza cu parsatul citirii?imi poate da cineva un exemplu
Multumesc!!!

Cred ca ai incurcat m-ul cu n-ul la un moment dat. Mi se pare ca for-urile din cuplaj trebuie sa se duca pana la m.

am modificat ,dar tot 0 pct iau  

  :'(am verificat de 100 ori sursa si nu vad o greseala.rog un admin sa se uite peste sursa sa vada ce am gresit
Multumesc anticipat!

Cod:

#include<fstream>
#include<cstring>
#include<vector>

#define NN 10001
#define pb push_back

using namespace std;
ofstream out("java.out");

int  n,m,e,t,uz[NN],dr[NN],st[NN];
vector<int>G[NN];
typedef vector<int>:: iterator IT;

void read();
int pairup(int start);
int facuplaj();

int main()
{
	read();
	return 0;
	
	
}

int pairup(int start)
{
	if(uz[start])
		return 0;
	uz[start]=1;
		for(IT I=G[start].begin();I!=G[start].end();++I)
			if(!st[*I] || pairup(st[*I]) )
			{
				st[*I]=start;
				dr[start]=*I;
				return 1;
			}
			return 0;
}

int facuplaj()
{
	int ok=1;
	int cuplaj=0;
	while(ok)
	{
		ok=0;
		memset(uz,0,sizeof(uz));
		for(int i=1;i<=n;i++)
			if(!dr[i] && pairup(i))
			{
				++cuplaj;
				ok=1;
			}
	}
	return cuplaj;
}


void read()
{
	ifstream in("java.in");
	in>>t;
	while(t)
		
	{
		
	in>>m>>n>>e;
	for(int x,y,i=1;i<=e;i++)
	{
		in>>x>>y;
		G[x].pb(y);
		
	}
	
	facuplaj();
	int nrc=0;
	for(int i=1;i<=n;i++)
		if(dr[i])
			++nrc;
		out<<nrc<<'\n';
			//out<<i<<" "<<dr[i]<<" "<<'\n';

	t--;
	}
}

Nu cred ca e bine cum spui tu, adica cu sortatul in ordine crescatoare in functie de x.
Uite un contraexemplu:

2 2
3 1
6 2
7 100

Daca iei in ordine crescatoare obtii 1831. Se mai pot obtine si rezultate mai mici, precum: ..., 778, 766.
Mai degraba as inclina sa sortez descrescator dupa y.
L.E. Done! Nu era chiar asa, dar pe aproape cu acea sortare...

pana la urma cum trebuie sa sortezi? ](*,)am sortat in mai multe feluri....  imi dau bine pe testul de la problema(chiar si  pe al tau) dar tot 0 iau

au fost publicate solutiile oficiale la runda a 2-a?

Greseala e in sortare. Sirul il sortezi in functie de ambele valori. Incearca sa gasesti o legatura intre x si y; cu cat contribuie fiecare pereche in realizarea costului final; si in functie de acea legatura sortezi

de 1h tot incerc faza cu sortarea si nu iese
mai incerc maine:D
mersi oricum pt idee
noapte buna

Salut ! Ma poate ajuta si pe mine cineva? am sortat crescator dupa x i-ar in caz de egalitate descrescator dupa y.
L.E. : Mi-a iesit pana la urma.

am sortat descrescator vectorul in functie de y iar in caz de egalitate crescator in functie de x
Functia care calculeaza este urmatoare:
....

for(int i=1;i<=n;i++)
   {
      int s=0;
      for(int j=1;j<=i;j++)
         s+=G[j].x;
   
      ans+=s*G.y;
      
   }

..
iau 0 pct si nu stiu dc
Imi puteti da o sugestie?
Multumesc anticipat!!!