[AtCoder]TLEを解消出来ません[解消済み]
Q&A
Closed
質問
AtCoderでどうしてもTLEになります。
解説を読み、考え方は間違っていないと思いますが、コピペはいろいろよろしくないので、どうにか自身でやりたかったのですが自分の実力じゃだめでした。
どこがネックになっているのかを教えていただきたいです。
問題URL「ABC353C問題、Sigma Problem」
以下がコードです。
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
using ll = long long;
int main(void)
{
int n;
cin >> n;
vector<int> a(n);
for(int i = 0; i < n; i++) cin >> a[i];
sort(a.begin(), a.end());
int r = n-1, l = r-1;
ll count = 0;
while(r > 0)
{
while(a[r]+a[l] >= 100000000 && l >= 0) l--;
count += r-l-1;
if(r == l+1) break;
r--;
l = r-1;
}
ll sum = 0;
for(int i = 0; i < n; i++) sum += ll(a[i]) * (n-1);
sum -= ll(count) * 100000000;
cout << sum << endl;
return 0;
}
備考
私の考えでは二重ループがやはり良くないのではと考えていますが、解説でも二重ループは使っていますし、それ以外の案が思い浮かびません。
1:私のコードと解説のコードでは何が違うのか
2:そもそも二重ループを使わない方法はないのか
この二点についてももしお答えいただけるのであれば幸いです。
また、今回初めてQiitaで質問を作成したのですが、質問のしかたに問題があればご指摘いただけると今後の役に立ちますのでよろしくお願いいたします。
0
