Submission #995292


Source Code Expand

Copy
#define _CRT_SECURE_NO_WARNINGS
#include "bits/stdc++.h"
using namespace std;

#define int int64_t

#define CHOOSE(a) CHOOSE2 a
#define CHOOSE2(a0,a1,a2,a3,x,...) x
#define REP1(i, s, cond, cal) for (signed i = signed(s); i cond; i cal)
#define REP2(i, s, n) REP1(i, s, < signed(n), ++)
#define REP3(i, n) REP2(i, 0, n)
#define rep(...) CHOOSE((__VA_ARGS__,REP1,REP2,REP3))(__VA_ARGS__)
#define rrep(i, s) rep(i, s, >= 0, --)

#define all(c) begin(c), end(c)
#define maxup(ans, x) (ans = (ans < x ? x : ans))
#define minup(ans, x) (ans = (ans > x ? x : ans))

#define breakif(cond) if(cond) break; else

using VV = vector<vector<int>>;
using V = vector<int>;
using P = pair<int, int>;
using IP = pair<int, P>;

template<typename T>
inline void input(vector<T>& v) { for (auto& x : v) cin >> x; }

signed main() {
	int N, A; cin >> N >> A;
	if (N > 1000000 || A > 1000000) return 1;
	vector<P> memo(N + 1, P(0, 1));
	int ans = N;
	rep(i, N) {
		memo[i] = P(i, 1);
	}
	//n秒時点での最大の枚数,毎秒枚数
	rep(i, 1, N + 1) {
		int num = memo[i].first;
		int x = memo[i].second;
		ans = min(ans, i + (N - num - 1) / x + 1);
		if (i + 1 <= N) maxup(memo[i + 1], P(num + x, x));
		if (i - x <= 0) continue;
		int left = 0, right = N;
		while (left + 1 < right) {
			int mid = (left + right) / 2;
			bool ok = true;
			if (mid < i + A) ok = false;
			if (ok && memo[mid].first <= (mid - i - A) * num) right = mid;
			else left = mid;
		}
		memo[right] = max(memo[right], P((right - i - A) * num, num));
	}
	cout << ans << endl;

	system("pause");
}

Submission Info

Submission Time
Task E - Cookies
User tosaka2
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1609 Byte
Status
Exec Time 108 ms
Memory 16120 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:56:17: warning: ignoring return value of ‘int system(const char*)’, declared with attribute warn_unused_result [-Wunused-result]
  system("pause");
                 ^

Judge Result

Set Name Score / Max Score Test Cases
sample 0 / 0 sample-01.txt, sample-02.txt, sample-03.txt
dataset1 0 / 500 sample-01.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt
dataset2 0 / 500 sample-01.txt, sample-02.txt, sample-03.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 02-09.txt, 02-10.txt, 02-11.txt, 02-12.txt, 02-13.txt, 02-14.txt, 02-15.txt, 02-16.txt, 02-17.txt, 02-18.txt, 02-19.txt, 02-20.txt, 02-21.txt, 02-22.txt, 02-23.txt, 02-24.txt, 02-25.txt, 02-26.txt, 02-27.txt, 02-28.txt, 02-29.txt, 02-30.txt, 02-31.txt, 02-32.txt, 02-33.txt, 02-34.txt, 02-35.txt, 02-36.txt, 02-37.txt, 02-38.txt, 02-39.txt, 02-40.txt
Case Name Status Exec Time Memory
01-01.txt 40 ms 16120 KB
01-02.txt 106 ms 16120 KB
01-03.txt 106 ms 16116 KB
01-04.txt 107 ms 16120 KB
01-05.txt 108 ms 16120 KB
01-06.txt 107 ms 16120 KB
01-07.txt 108 ms 16120 KB
01-08.txt 106 ms 16120 KB
01-09.txt 107 ms 16120 KB
01-10.txt 107 ms 16120 KB
01-11.txt 107 ms 16120 KB
01-12.txt 79 ms 16120 KB
01-13.txt 80 ms 16120 KB
01-14.txt 9 ms 1400 KB
01-15.txt 22 ms 8696 KB
01-16.txt 57 ms 8696 KB
01-17.txt 105 ms 15872 KB
01-18.txt 4 ms 504 KB
01-19.txt 4 ms 500 KB
01-20.txt 4 ms 504 KB
01-21.txt 4 ms 504 KB
01-22.txt 4 ms 504 KB
01-23.txt 4 ms 500 KB
01-24.txt 4 ms 504 KB
01-25.txt 4 ms 504 KB
01-26.txt 4 ms 504 KB
02-01.txt 2 ms 256 KB
02-02.txt 2 ms 256 KB
02-03.txt 2 ms 256 KB
02-04.txt 2 ms 256 KB
02-05.txt 2 ms 256 KB
02-06.txt 3 ms 256 KB
02-07.txt 2 ms 256 KB
02-08.txt 2 ms 256 KB
02-09.txt 2 ms 256 KB
02-10.txt 2 ms 256 KB
02-11.txt 2 ms 256 KB
02-12.txt 2 ms 256 KB
02-13.txt 2 ms 256 KB
02-14.txt 2 ms 256 KB
02-15.txt 2 ms 384 KB
02-16.txt 2 ms 256 KB
02-17.txt 2 ms 256 KB
02-18.txt 2 ms 256 KB
02-19.txt 2 ms 256 KB
02-20.txt 2 ms 256 KB
02-21.txt 2 ms 256 KB
02-22.txt 2 ms 256 KB
02-23.txt 2 ms 256 KB
02-24.txt 2 ms 256 KB
02-25.txt 3 ms 256 KB
02-26.txt 2 ms 256 KB
02-27.txt 2 ms 256 KB
02-28.txt 2 ms 256 KB
02-29.txt 3 ms 256 KB
02-30.txt 2 ms 256 KB
02-31.txt 2 ms 256 KB
02-32.txt 2 ms 256 KB
02-33.txt 2 ms 256 KB
02-34.txt 2 ms 256 KB
02-35.txt 2 ms 256 KB
02-36.txt 2 ms 256 KB
02-37.txt 2 ms 256 KB
02-38.txt 2 ms 256 KB
02-39.txt 2 ms 256 KB
02-40.txt 2 ms 256 KB
sample-01.txt 4 ms 504 KB
sample-02.txt 2 ms 256 KB
sample-03.txt 16 ms 2424 KB