Задача на codeforces на проходит по времени?

Question

[leean]

не проходит по времени, не знаю что делать вообще. Задача рассчитана на жадный алгоритм.
https://codeforces.com/problemset/problem/1132/B

#include <bits/stdc++.h>
using namespace std;
int main ()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    vector<long long> a,b;
    long long i,j,k,n,m,l=0;
    cin>>n;

    for(i=0;i<n;++i){
        cin>>k;
        a.push_back(k);
    }
    cin>>m;

    for(i=0;i<m;++i){
        cin>>k;
        b.push_back(k);
    }

    sort(a.begin(),a.end());

    for(i=0;i<m;++i){
        for(j=n-b[i];j<n;++j){
            l=l+a[j];
        }
        l=l-a[n-b[i]];
        for(j=0;j<n-b[i];++j){
            l=l+a[j];
        }
        cout<<l<<endl;
        l=0;
    }
    return 0;
}

Answer 1

[Wataru]

У вас решение за O(NM), когда как есть решение за O(N+M).

Вы считаете сумму всех цен каждый раз. Но это делать не обязательно, ведь вам надо найти сумму всех цен, кроме одной. Можно подсчитать сумму всех один раз и потом вычитать из нее лишнюю цену (но надо аккуратно подумать о переполнениях). Или можно воспользоватся префиксными и постфиксными суммами.

Comments

[leean]

спасибо, сейчас попробую

[leean]

спасибо, помогло, прошла на полный бал.
Вот код если кто сталкнётся с таким:

#include <bits/stdc++.h>
using namespace std;
int main ()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    vector<long long> a, b;
    long long i,j,k,n,m,l=0,sum=0;
    cin>>n;
 
    for(i=0;i<n;++i){
        cin>>k;
        a.push_back(k);
    }
    cin>>m;
    for(i=0;i<m;++i){
        cin>>k;
        b.push_back(k);
    }
    l=0;
    sort(a.begin(),a.end());
    for(i=0;i<n;++i){
        sum=sum+a[i];
    }
    n;
    for(i=0;i<m;++i){
        cout<<sum-a[n-b[i]]<<endl;
    }
 
    return 0;
}