QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#184606#3872. Gym BadgesTalaodi0 15ms101888kbC++144.8kb2023-09-20 22:29:522023-09-20 22:29:53

Judging History

This is the latest submission verdict.

  • [2023-09-20 22:29:53]
  • Judged
  • Verdict: 0
  • Time: 15ms
  • Memory: 101888kb
  • [2023-09-20 22:29:52]
  • Submitted

answer

#include <bits/stdc++.h>

char __ST__;

namespace IO {
	template <class Stream>
	Stream& fmtbase(Stream& out, const char* format) {
		for (; *format; format++) {
			if (*format == '{' && *(format + 1) == '}') {
				throw std::invalid_argument("Error Number of Parameters!");
			}
			
			out << *format;
		}
		
		return out;
	}
	
	template <class Stream, class Fst, class... Nxt>
	Stream& fmtbase(Stream& out, const char* format, const Fst& value, const Nxt&... nxt) {
		for (; *format; format++) {
			if (*format == '{' && *(format + 1) == '}') {
				out << value;
				return fmtbase(out, format + 2, nxt...);
			} 
			
			out << *format;
		}
		
		throw std::invalid_argument("Error Number of Parameters!");
	}
	
	template <class... Ps>
	std::string to_string(const char* format, const Ps&... ps) {
		std::stringstream ss;
		fmtbase(ss, format, ps...);
		return ss.str();
	}

	template <class... Ps>
	std::ostream& fmtout(const char* format, const Ps&... ps) {
		return fmtbase(std::cout, format, ps...);
	}
	
	template <class... Ps>
	std::ostream& fmterr(const char* format, const Ps&... ps) {
		return fmtbase(std::cerr, format, ps...);
	}
	
	std::istream& allin() {
		return std::cin;
	}
	
	template <class Fst, class ... Nxt>
	std::istream& allin(Fst& fst, Nxt&... nxt) {
		std::cin >> fst;
		return allin(nxt...);
	}
	
	template <class Iter>
	std::istream& rangin(Iter begin, Iter end) {
		while (begin != end) {
			std::cin >> *begin;
			begin++;
		}
		
		return std::cin;
	}
	
	namespace Fast {
		bool sync = false;
		
		char buf[1 << 23];
		char *p1 = buf, *p2 = buf;
		
		void sync_with_ios(bool s) {
			sync = s;
		}
		
		char getchar() {
			if (sync) {
				return (char) std::cin.get();
			}
			else {
				if (p1 == p2) {
					p1 = buf;
					p2 = p1 + fread(buf, 1, 1 << 22, stdin);
				}
				
				if (p1 == p2) {
					return EOF;
				}
				else {
					char res = *p1;
					p1++;
					return res;
				}
			}
		}
		
		void read() { }
		
		template <class T, class... U>
		void read(T& x, U&... us) {
			x = 0;
			T pos = 1;
			
			char c = getchar();
			while (!isdigit(c)) {
				if (c == '-') {
					pos = -1;
				}
				
				c = getchar();
			}
			
			while (isdigit(c)) {
				x = 10 * x + c - '0';
				c = getchar();
			}
			
			x *= pos;
			read(us...);
		}
		
		template <class T>
		void write(const T& t) {
			if (t > 10) {
				write(t / 10);
			}
			
			std::cout << (int) (t % 10);
		}
	}
}

namespace Solve {
	using namespace IO;

	using ll = long long;
	using ul = unsigned long long;
	using db = double;
	using ld = long double;
	using ui = unsigned int;
	using ib = __int128;
	using ub = __uint128_t;

	int const INF = std::numeric_limits<int>::max();
	int const NINF = std::numeric_limits<int>::min();
	ll const LINF = std::numeric_limits<ll>::max();
	ll const LNINF = std::numeric_limits<ll>::min();
	ld const EPS = 1e-6;

	template <class T>
	inline int isz(const T& v) {
		return v.size();
	}

	std::mt19937 mt(std::chrono::high_resolution_clock::now().time_since_epoch().count());

	ll rnd(ll l, ll r) {
		return std::uniform_int_distribution<ll>(l, r)(mt);
	}

	int const N = 5e3 + 10;

	struct Val {
		int L, X;
	};

	Val v[N + 1];
	int f[N + 1][N + 1];
	int n;

	void main() {
		std::cin >> n;
		for (int i = 1; i <= n; i++) {
			std::cin >> v[i].X;
		}

		for (int i = 1; i <= n; i++) {
			std::cin >> v[i].L;
		}

		std::sort(v + 1, v + n + 1, [&](const Val& a, const Val& b) {
			return a.L + a.X < b.L + b.X;
		});

		for (int i = 0; i <= n; i++) {
			for (int j = 0; j <= n; j++) {
				f[i][j] = INF;
			}
		}

		f[0][0] = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j <= i; j++) {
				if (f[i][j] == INF) {
					continue;
				}

				if (f[i][j] <= v[i + 1].L) {
					f[i + 1][j + 1] = std::min(f[i + 1][j + 1], f[i][j] + v[i + 1].X);
				}

				f[i + 1][j] = std::min(f[i + 1][j], f[i][j]);
			}
		}

		for (int i = 2; i <= n; i++) {
			if (f[n][i] == INF) {
				break;
			}

			assert(f[n][i] - f[n][i - 1] >= f[n][i - 1] - f[n][i - 2]);
		}
	}

	void init() {

	}

	void clear() {

	}
}

char __ED__;

signed main() {
#ifndef ONLINE_JUDGE
	auto input_file = freopen("d.in", "r", stdin);
	auto output_file = freopen("d.out", "w", stdout);
#endif
	
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	
	int t = 1;
	// std::cin >> t;

	Solve::init();
	
	for (int id = 1; id <= t; id++) {
		Solve::main();
		Solve::clear();
	}

#ifndef ONLINE_JUDGE
	std::cout.flush();
	fclose(input_file);
	fclose(output_file);
#endif

#ifndef ONLINE_JUDGE
	IO::fmterr("{}{}static memory usage: {} MB.\n", std::fixed, std::setprecision(3), (&__ST__ - &__ED__) / 1024. / 1024);
#endif
	
	return 0;
}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 5836kb

input:

8
539270098 632706230 269629236 114860227 516388668 106926736 442326081 489479590
349109371 304195858 1 1 1 1 1 272176035

output:


result:

wrong answer 1st lines differ - expected: '2', found: ''

Subtask #2:

score: 0
Runtime Error

Test #21:

score: 0
Runtime Error

input:

499024
24194059 58419582 93795671 46748573 538530 94101772 6557176 45861806 13697565 74131600 86230763 495874 93328371 85034659 58261516 3311420 83620814 92145308 62793177 67970802 63891191 62175600 59686038 44916927 32817940 23191454 40796822 55385422 97662235 82408332 33350127 65553532 70025555 47...

output:


result:


Subtask #3:

score: 0
Wrong Answer

Test #41:

score: 0
Wrong Answer
time: 15ms
memory: 101888kb

input:

4920
343676952 471362068 183764630 14272498 286605010 453007536 667797750 174763306 161753738 692259390 402384334 207809675 24816038 135559720 2349171 268297289 158915976 311483232 237276350 130673100 523233652 177852180 84082840 350906472 27172979 107661274 8628817 205814954 636498502 115751626 451...

output:


result:

wrong answer 1st lines differ - expected: '200', found: ''

Subtask #4:

score: 0
Skipped

Dependency #1:

0%