結果

問題 No.949 飲酒プログラミングコンテスト
ユーザー f1b_maxbl00df1b_maxbl00d
提出日時 2020-03-11 22:46:30
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 236 ms / 2,500 ms
コード長 1,818 bytes
コンパイル時間 1,474 ms
コンパイル使用メモリ 139,552 KB
実行使用メモリ 73,728 KB
最終ジャッジ日時 2024-04-27 20:45:53
合計ジャッジ時間 5,434 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 1 ms
6,944 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 1 ms
6,944 KB
testcase_07 AC 1 ms
6,944 KB
testcase_08 AC 2 ms
6,940 KB
testcase_09 AC 2 ms
6,940 KB
testcase_10 AC 2 ms
6,940 KB
testcase_11 AC 162 ms
53,120 KB
testcase_12 AC 167 ms
54,016 KB
testcase_13 AC 139 ms
47,744 KB
testcase_14 AC 18 ms
9,344 KB
testcase_15 AC 97 ms
37,504 KB
testcase_16 AC 193 ms
67,200 KB
testcase_17 AC 20 ms
11,264 KB
testcase_18 AC 223 ms
70,528 KB
testcase_19 AC 150 ms
53,632 KB
testcase_20 AC 28 ms
13,696 KB
testcase_21 AC 11 ms
7,552 KB
testcase_22 AC 22 ms
12,288 KB
testcase_23 AC 4 ms
6,940 KB
testcase_24 AC 103 ms
39,808 KB
testcase_25 AC 233 ms
73,728 KB
testcase_26 AC 236 ms
73,728 KB
testcase_27 AC 221 ms
73,728 KB
testcase_28 AC 235 ms
73,728 KB
testcase_29 AC 213 ms
73,600 KB
testcase_30 AC 194 ms
73,728 KB
testcase_31 AC 193 ms
73,728 KB
testcase_32 AC 223 ms
73,728 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <limits.h>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <queue>
#include <map>
#include <set>
#include <iomanip>
#include <bitset>
#include <cassert>
#include <random>
#include <functional>
#include <stack>
#include <iomanip>
#include <cassert>
//#include <boost/multiprecision/cpp_int.hpp>
#include <complex>
#include <cstdio>
#include <list>

//< in.txt > out.txt
using namespace std;
//std::ios::sync_with_stdio(false);
//std::cin.tie(0);
const long long MOD = 1e9 + 7;
typedef long long LL;
typedef long double LD;
typedef pair<LL, LL> PLL;
typedef pair<LD, LL> PDL;
typedef pair<LD, LD> PDD;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;
//typedef boost::multiprecision::cpp_int bigint;

template<class T>
void in(T& x) {
	cin >> x;
}

template<class T1, class T2>
void in(pair<T1, T2>& p) {
	in(p.first);
	in(p.second);
}

template<class T>
void in(vector<T>& v, LL st = -1, LL en = -1) {
	if (st == -1) {
		st = 0;
		en = v.size() - 1;
	}
	for (LL n = st; n <= en; n++) {
		in(v[n]);
	}
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	LL N;
	cin >> N;
	VLL A(N+1), B(N+1), D(N+1);
	in(A,0,N);
	in(B,0,N);
	in(D,1,N);
	sort(D.begin(), D.end(), [](LL a, LL b) {
		return a < b;
	});
	VVLL DP;
	DP.resize(N + 1, VLL(N + 1, N + 2));
	LL ans = 0;
	for (LL k = 1; k <= N; k++) {
		for (LL x = 0; x <= k; x++) {
			LL y = k - x;
			LL sum = A[x] + B[y];
			LL s = 0, e = N+1;
			while (e - s > 1) {
				LL m = (e + s) / 2;
				if (D[m] <= sum)s = m;
				else e = m;
			}
			LL prev = 0;
			if (x > 0) {
				prev = max(DP[x - 1][y], prev);
			}
			if (y > 0) {
				prev = max(DP[x][y - 1],prev);
			}
			DP[x][y] = min(s, prev - 1);
			if (DP[x][y] >= 1)ans = k;
		}
	}
	cout << ans << "\n";
	return 0;
}
0