結果

問題 No.370 道路の掃除
ユーザー aaa
提出日時 2019-01-04 16:34:58
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,788 bytes
コンパイル時間 1,297 ms
コンパイル使用メモリ 101,984 KB
実行使用メモリ 13,640 KB
最終ジャッジ日時 2024-11-23 23:12:42
合計ジャッジ時間 42,416 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 7 WA * 14 TLE * 13
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:134:39: warning: 'index' may be used uninitialized [-Wmaybe-uninitialized]
  134 |         func1(index, 1, abs(list[index]));
      |                                       ^
main.cpp:109:13: note: 'index' was declared here
  109 |         int index;
      |             ^~~~~

ソースコード

diff # 

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <functional>
#include <map>
#include <iomanip>
#include <math.h> 
#include <stack>
#include <queue>
#include <bitset>
#include <cstdlib>
#include <tuple>
#include <cctype>
#include <ctype.h>
#include <set>
#include <sstream>
#include <time.h>
using namespace std;
//#define int long long
#define rep(i,s,n) for(int i = s;i<n;i++)
#define repe(i,s,n) for(int i = s;i<=n;i++)
#define rrep(i,s,n) for(int i = (n)-1;i>=(s);i--)
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define fi first
#define se second
#define chmin(a,b) a=min((a),(b))
#define chmax(a,b) a=max((a),(b))
typedef long long ll;
typedef pair<int, int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
typedef pair<pint, int> P1;
typedef pair<int, pint> P2;
typedef pair<pint, pint> PP;
static const ll maxLL = (ll)1 << 62;
const ll MOD = 1000000007;
const ll INF = 1e18;
int ca[12] = { 31,28,31,30,31,30,31,31,30,31,30,31 };

int n, m, minn = 99999999;
vector<int>list;

struct MyStruct
{
	bool flag[1005];
};

int func1(int index, int cnt, int sum) {

	if (cnt == n) {
		minn = min(minn, sum);
		return 0;
	}

	if (index < 1) {
		func1(index + 1, cnt + 1, sum + abs(list[index] - list[index + 1]));
	}
	else {

		if (abs(list[index] - list[index - 1]) < abs(list[index] - list[index + 1])) {
			func1(index - 1, cnt + 1, sum + abs(list[index] - list[index - 1]));
		}
		else if (abs(list[index] - list[index - 1]) > abs(list[index] - list[index + 1])) {
			func1(index + 1, cnt + 1, sum + abs(list[index] - list[index + 1]));
		}
		else if (abs(list[index] - list[index - 1]) == abs(list[index] - list[index + 1])) {
			func1(index - 1, cnt + 1, sum + abs(list[index] - list[index - 1]));
			func1(index + 1, cnt + 1, sum + abs(list[index] - list[index + 1]));
		}

	}


	return 0;
}

int func2(int index, int cnt, int sum, MyStruct st) {

	if (sum >= minn) {
		return 0;
	}

	if (cnt == n) {
		minn = min(minn, sum);
		return 0;
	}

	for (int i = 0; i < m; i++) {
		if (st.flag[i] == false) {
			st.flag[i] = true;
			func2(i, cnt + 1, sum + abs(list[index] - list[i]), st);
		}
	}





	return 0;
}


signed main() {
	int i, j;
	int index;

	MyStruct st;

	memset(st.flag, 0, sizeof(st.flag));

	cin >> n >> m;

	for (i = 0; i < m; i++) {
		int num;
		cin >> num;
		list.push_back(num);
	}

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

	for (i = 0; i < m; i++) {
		if (minn > abs(0 - list[i])) {
			index = i;
			minn = abs(list[i]);
		}
	}

	minn = 99999999;

	func1(index, 1, abs(list[index]));

	for (i = 0; i < m; i++) {
		st.flag[i] = true;
		func2(i, 1, abs(list[i]), st);
		st.flag[i] = false;
	}

	



	cout << minn << endl;
















	getchar();
	getchar();
	return 0;
}
0