pistone's blog

MIPT ELJUDGE athletes problem solution optimisation
By pistone, 13 years ago, In English

here is my solution for thi problem from EL JUDGE ,
but the time limit is exceeds by 1 second , 


#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;

typedef struct{
 int m;
 int s;
}rec;

bool compare(const rec& r1,const rec& r2)
{
 return(r1.m + r1.s <= r2.m + r2.s);

}

int main()
{
 int n,i,j;
 int best[100000] ;

 cin>>n;
 i = 0;
 vector<rec> v;
 rec r;
 while(i < n)
 {
  //cin>>r.m;
  //cin>>r.s;
  scanf("%d",&r.m);
  scanf("%d",&r.s);
  v.push_back(r);
  i++;
 }
 for(i = 0;i<=n;i++)
  best[i] = 4000000;
 best[0] = 0;

 sort(v.begin(),v.end(),compare);
 int maxcount = 0;
 for(i= 0; i < n;i++)
 {
  for(j = maxcount + 1; j > 0;j--)
  {

   if(v[i].s >= best[j -1] && (v[i].m + best[j -1] < best[j]))
   {
    best[j] = v[i].m + best[j -1];
    if(j > maxcount) maxcount = j;
   }

  }

 }
 cout<<maxcount<<endl;
 return 0;
}



need  help to optimise this ,  the input length can be upto 100000

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Try to reserve space for v, like this:

vector<rec> v;
v.reserve(100000);
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
still getting TLE
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    it looks like there can be done O(n^2) operations  at  for(i ...)  for (j ...)
    → Reply