312 Sume 2

[•Bogdan_tmm]

Sa zicem ca suma fixata este S. Pentru a afla cate sume sunt mai mici ca aceasta, pentru fiecare element din vector trebuie sa vedem cate elemente din acelasi vector sunt mai mici sau egale cu S - element_curent si cate sunt strict  mai mici decat S - element_curent. Sumele acestor valori sa le notam cu upper si lower. Tot ce mai trebuie facut este sa verificam daca lower < k && k <= upper.

[•CosminRusu]

Cod:

#include <fstream>
using namespace std;
int main()
{
    ifstream cin("sume2.in");
    ofstream cout("sume2.out");
    int A[100005], i, j, S[100005], o, aux, a=0;
    long long k, n;
    cin>>n;
    cin>>k;
    for(i=1;i<=n;i++)
      cin>>A[i];
    for(i=1;i<=n;i++)
     {
       for(j=1;j<=n;j++)
          S[j+a]=A[i]+A[j];
       a=i*n;
     }  
do
{
 o=1;
 for(i=1;i<n*n;i++)
  if(S[i]>S[i+1])
  {
   o=0;
   aux=S[i];
   S[i]=S[i+1];
   S[i+1]=aux;
   }
}while(!o);
cout<<S[k]<<"\n";
cin.close();
cout.close();

return 0;
}

Ce am gresit ? La celelalte 8 imi da Killed by signal!

[•klamathix]

N-ul e 50 000. Ce-ti spune asta despre N ^ 2?

[•teodor98]

Am probleme cu limitele  daca pun int iau 40p ( http://www.infoarena.ro/job_detail/1088260 ) , daca pun unsigned int iau 60p (http://www.infoarena.ro/job_detail/1088263) cu killbysem la primele 4 pot (      ) si daca pun long long iau 0p 

[•freak93]

Nu e de la limite. Ai tu greseli in program. Ti-am gasit destul de repede greseala in program si nu iti voi spune care este dintr-un motiv foarte simplu. NU inveti nimic din asta.

 Incearca sa te uiti prin codul tau la fiecare linie scrisa sa-ti gasesti greseala. Daca nu poti asa, invata sa-ti scrii un generator de teste, pentru problema asta e foarte simplu, functiile srand si rand (le poti cauta pe cplusplus.com) sunt aici ca sa te ajute. Dupa poti sa faci si un mini-evaluator (un program care genereaza, ruleaza sursa ta si iti spune daca a rulat bine sau nu), unde aici iti este prietena functia system (pe care din nou o poti cauta pe cplusplus.com). Rog si ca nimeni altcineva sa nu-ti raspunda exact cu problema insasi, singura chestie pe care o castigi sunt inca 40 de puncte, cand ai putea castiga niste experienta.

[•Djok]

Complexitatea necesară pentru 100p este O(N logN)?
Cu O(N log^2N) iau doar 60p  

Edit: am optimizat un pic, și a mers.

[•dragona15]

Poate sa ma ajute si pe mine cineva cu problema asta imi trebuie o varianta cat mai optima?