結果

問題 No.107 モンスター
ユーザー snteasntea
提出日時 2016-10-13 20:21:56
言語 C++11
(gcc 11.4.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 2,886 bytes
コンパイル時間 2,106 ms
コンパイル使用メモリ 172,288 KB
実行使用メモリ 222,976 KB
最終ジャッジ日時 2024-06-01 04:37:53
合計ジャッジ時間 9,163 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 1 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 1 ms
5,376 KB
testcase_08 WA -
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 1 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 227 ms
51,712 KB
testcase_14 AC 374 ms
106,880 KB
testcase_15 AC 376 ms
107,008 KB
testcase_16 AC 2 ms
5,376 KB
testcase_17 AC 95 ms
25,856 KB
testcase_18 AC 1,046 ms
222,976 KB
testcase_19 AC 1,044 ms
222,976 KB
testcase_20 AC 165 ms
51,712 KB
testcase_21 AC 175 ms
51,712 KB
testcase_22 AC 518 ms
106,880 KB
testcase_23 AC 910 ms
222,976 KB
testcase_24 AC 1,165 ms
222,976 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#ifdef LOCAL111
#else
	#define NDEBUG
#endif
#include <bits/stdc++.h>
const int INF = 1e9;
using namespace std;
template<typename T, typename U> ostream& operator<< (ostream& os, const pair<T,U>& p) { cout << '(' << p.first << ' ' << p.second << ')'; return os; }

#define endl '\n'
#define ALL(a)  (a).begin(),(a).end()
#define SZ(a) int((a).size())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#define RBP(i,a) for(auto& i : a)
#ifdef LOCAL111
	#define DEBUG(x) cout<<#x<<": "<<(x)<<endl
	template<typename T> void dpite(T a, T b){ for(T ite = a; ite != b; ite++) cout << (ite == a ? "" : " ") << *ite; cout << endl;}
#else
	#define DEBUG(x) true
	template<typename T> void dpite(T a, T b){ return; }
#endif
#define F first
#define S second
#define SNP string::npos
#define WRC(hoge) cout << "Case #" << (hoge)+1 << ": "
#define rangej(a,b,c) ((a) <= (c) and (c) < (b))
#define rrangej(b,c) rangej(0,b,c)
template<typename T> void pite(T a, T b){ for(T ite = a; ite != b; ite++) cout << (ite == a ? "" : " ") << *ite; cout << endl;}
template<typename T> bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;}
template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;}

typedef long long int LL;
typedef unsigned long long ULL;
typedef pair<int,int> P;
typedef pair<LL,LL> LP;

void ios_init(){
	//cout.setf(ios::fixed);
	//cout.precision(12);
#ifdef LOCAL111
	return;
#endif
	ios::sync_with_stdio(false); cin.tie(0);	
}

vector<int> bit_toposort(int n)
{
	vector<int> res;
	res.reserve(1<<n);
	vector<bool> used(1<<n,false);
	function<void(int)> rec = [&](int mask){
		used[mask] = true;
		for(int i = 0; i < n; ++i) {
			if(!((mask>>i)&1)){
				if(!used[mask|(1<<i)]) rec(mask|(1<<i));
			}
		}
		res.push_back(mask);
		return;
	};
	rec(0);
	return res;
}

int main()
{
	ios_init();
	int n;
	bitset<1600> bits[17];
	REP(i,1600) bits[0][i] = true;
	REP(i,16){
		bits[i+1] = bits[i]<<100;
	}
	REP(i,17) DEBUG(bits[i]);
	while(cin >> n){
		vector<int> d(n);
		REP(i,n) cin >> d[i];
		using vb = bitset<1600>;
		vector<vector<vb>> dp((1<<n),vector<vb>(n+1));
		dp[(1<<n)-1][0][99] = true;
		auto topo = bit_toposort(n);
		dpite(ALL(topo));
		REP(i,SZ(topo)){
			int mask = topo[i];
			if(mask == (1<<n)-1) continue;
			DEBUG(bitset<16>(mask));
			REP(j,n+1){
				REP(k,n) if(!((mask>>k)&1)){
					DEBUG(k);
					if(d[k] < 0){
						if(j) dp[mask][j] |= dp[mask|(1<<k)][j-1]>>(-d[k]);
					} else {
						auto t = dp[mask|(1<<k)][j]<<d[k];
						if((t&bits[j+1]) != 0){
							t[100*(j+1)-1] = true;
							t &= ~bits[j+1];
						}
						dp[mask][j] |= t;
					}
				}
			}
		}
		int ans = 0;
		REP(i,n+1) RREP(j,1600){
			if(dp[0][i][j]){
				ans = max(ans,j+1);
				break;
			}
		}
		cout << ans << endl;
	}
	return 0;
}
0