結果
問題 | No.270 next_permutation (1) |
ユーザー |
![]() |
提出日時 | 2020-11-12 09:17:39 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 71 ms / 2,000 ms |
コード長 | 1,572 bytes |
コンパイル時間 | 1,941 ms |
コンパイル使用メモリ | 170,596 KB |
実行使用メモリ | 5,732 KB |
最終ジャッジ日時 | 2024-07-22 19:03:39 |
合計ジャッジ時間 | 3,685 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 15 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define MAX_N 100001typedef long long ll;ll s[MAX_N];vector<ll> vp, vb;int N, K;template<typename It>ll my_next_permutation(It begin, It end){if (begin == end) return 0;It i = begin;++i;if (i == end) return abs(vp[0] - vb[0]);i = end;--i;while (true){It j = i;--i;if (*i < *j){It k = end;while (!(*i < *--k)) /* pass */;iter_swap(i, k);reverse(j, end);// sumを更新するfor(int k=distance(begin, i)-1; k<N-1; k++){if(k == -1) s[k+1] = abs(vp[k+1] - vb[k+1]);else s[k+1] = s[k] + abs(vp[k+1] - vb[k+1]);}return s[N-1];}if (i == begin){reverse(begin, end);// sumを更新するs[0] = abs(vp[0] - vb[0]);for(int k=0; k<N-1; k++) s[k+1] = s[k] + abs(vp[k+1] - vb[k+1]);return s[N-1];}}}int main(void){cin >> N >> K;ll ret = 0;for(int i=0; i<N; i++){int p; cin >> p;vp.push_back(p);}for(int i=0; i<N; i++){int b; cin >> b;vb.push_back(b);}if(K-- > 0){// sumを更新するs[0] = abs(vp[0] - vb[0]);for(int k=0; k<N-1; k++) s[k+1] = s[k] + abs(vp[k+1] - vb[k+1]);ret += s[N-1];}for(int k=0; k<K; k++){ret += my_next_permutation(vp.begin(), vp.end());}cout << ret << endl;}