ABC092 C Traveling Plan 累積和を取って計算量削減
ABC092 C Traveling Plan
問題概要
リンク参照
考察
- 愚直に計算するとかかるので計算量削減が必要.どう減らすか?
- 観光スポットを削除する部分以外は毎回コストは変わらないので毎回計算するのは無駄
- 今回は観光スポットを消さない場合のコストの総和(sumとする)を前処理で求めておいて,観光スポットiを消す場合について,sum-(観光スポットをiとi+1の間のコスト)-(観光スポットをiとi-1の間のコスト)+(観光スポットをi-1とi+1の間のコスト)を出力すればで間に合う
なお,バグりました
うく
ソースコード
#include<iostream> #include<vector> #include<algorithm> #include<cctype> #include<utility> #include<string> #include<cmath> #include<cstring> #include<queue> #include<map> #include<set> #include<climits> using namespace std; typedef long long int ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define ARRAY_MAX 100005 const int INF = INT32_MAX / 3; const ll MOD = 1e9 + 7; int dx[4] = { 1,0,0,-1 }; int dy[4] = { 0,1,-1,0 }; /******************************************************************************************/ int main() { int n; cin >> n; vector<int> a; a.push_back(0); ll sum = 0; for (int i = 0; i < n; i++) { int c; cin >> c; a.push_back(c); } a.push_back(0); n += 2; for (int i = 0; i <= n - 2; i++) { sum += abs(a[(i + 1) % n] - a[i]); } for (int i = 1; i <= n - 2; i++) { cout << sum - abs(a[(i + 1) % n] - a[i]) - abs(a[i] - a[(i + n - 1) % n]) + abs(a[(i + 1) % n] - a[(i + n - 1) % n]) << endl; } return 0; }