1

I have been struggling with it for 2 days.Please, could anyone tell me why does it exceed the time limit when i use as input 20000 and 0 and 40000 numbers afterwards ? I tried to make the variables type as large as possible, but that does not seem to help either.

#include <bits/stdc++.h>

using namespace std;

int main()
{
    /*freopen("file.in", "r", stdin);
    freopen("file.out", "w" , stdout);*/
    long long int aux,i, n, k, j, total = 0;
    cin >> n >> k;
    long long int a[n], b[n], order[n];
    signed long long int profit[n];
    for(i = 0; i < n; i++)
        cin >> a[i];
    for(i = 0; i < n; i++)
        cin >> b[i];
    for(i = 0; i < n; i++)
        profit[i] = a[i] - b[i];
    for(i = 0; i < n; i++)
        order[i] = i;
    for(i = 0; i < n; i++)
        for(j = i + 1; j < n; j++)
            if(profit[order[i]] > profit[order[j]])
            {
                aux = order[i];
                order[i] = order[j];
                order[j] = aux;
            }
    if(k > 0)
        for(i = 0; i < k; i++)
        {
            total += a[order[i]];
        }

    for(i = k; i < n; i++)
    {
        if(profit[order[i]] < 0)
            total += a[order[i]];
        else
            total += b[order[i]];
    }
    cout << total;

    return 0;
}
nnenthusiast
  • 15
  • 6
  • Have you profiled your code to determine where it's actually spending its time? – Andrew Henle Apr 04 '17 at 14:06
  • How do I do that ? – nnenthusiast Apr 04 '17 at 14:29
  • You can start by reading here: http://stackoverflow.com/questions/2229336/linux-application-profiling And `#include `?!?!? No, just no. Do not do that. See http://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h?noredirect=1&lq=1 – Andrew Henle Apr 04 '17 at 14:36
  • Thank you for letting me know about the second link :).You are a hero But i understand nothing from the first one.May I ask you to make the necessary sort ing method replacement in my code .I am at the begging , and understand code a lot easier if it`s written in my context.Please :,( – nnenthusiast Apr 04 '17 at 14:56
  • The biggest problem a beginner has is knowing where to look for answers. When you use shortcuts like `#include ` - aside from the issues in the link - you don't learn how to properly use things. For example, if you want to use a C++ `vector`, you need to `#include` the proper headers. If you want to use C-style system-call based IO such as `open()`/`read()`/`write()` - you have to learn how to identify the proper headers. For example, to use the C `open()` system call, you can use the `man open` command to see the manual page for `open`. – Andrew Henle Apr 04 '17 at 15:05
  • Ok.I will not use that header anymore.But can you please show me the code with merge sort instead of my bubble sort ? – nnenthusiast Apr 04 '17 at 15:20

1 Answers1

1

The complexity of your code is O(n^2), which is too much for N=20000. Reduce the complexity, replacing your bubble sort with Qsort. Try std::sort with custom comparison function.

Alexander Lapenkov
  • 585
  • 2
  • 9
  • How do I use std : sort ? I am not familiar with it. And quicksort doesn`t have the worst case scenerio of performance O(n^2) too ? – nnenthusiast Apr 04 '17 at 13:09
  • It depends on the implementation. When you pick random pivot element that takes O(n log n). If you want you can use merge sort or any sort with complexity O(log n) – Alexander Lapenkov Apr 04 '17 at 13:14