Submission #2361336


Source Code Expand

Copy
#include <bits/stdc++.h>
#define pq priority_queue
using namespace std;
constexpr long long gcd(long long a, long long b){return b ? gcd(b, a % b) : a;}
constexpr long long lcm(long long a, long long b){return a / gcd(a, b) * b;}
constexpr int INF = 1e9, MOD = INF + 7, around[] = {0, 1, 1, -1, -1, 0, -1, 1, 0, 0};
constexpr int mod_pow(long long x, long long n, const int mod){long long ret=1;while(n){if(n&1)(ret*=x)%=mod;(x*=x)%=mod;n>>=1;}return ret;}
template<int n> struct Prime{bool arr[n+1];constexpr bool operator[](int k){return arr[k];}constexpr Prime():arr(){for(int i=2;i<n;i++){arr[i]=true;for(int j=2;j*j<=i;j++){if(!(i%j))arr[i]=false;}}}};
template<int n> struct Factorial{long long arr[n+1],ary[n+1];constexpr Factorial():arr(),ary(){arr[0]=1;ary[0]=1;for(int i=0;i<n;i++){arr[i+1]=arr[i]*(i+1)%MOD;ary[i+1]=mod_pow(arr[i+1],MOD-2,MOD);}}};
constexpr Factorial<1010> fact; constexpr Prime<10> prime;
constexpr long long comb(int a, int b){if(a < b) return 0LL;if(!a or !b) return 1LL; long long pos = fact.arr[a], pot = fact.ary[a - b], por = fact.ary[b]; return pos * pot % MOD * por % MOD;}
template<int n> struct Bernoulli{long long arr[n+1];constexpr Bernoulli():arr(){arr[0]=1;for(int i=1;i<=n;i++){long long sum=0;for(int j=0;j<i;j++){(sum+=comb(i+1,j)*arr[j]%MOD)%=MOD;}arr[i]=(MOD-mod_pow(i+1,MOD-2,MOD))%MOD*sum%MOD;}}};
constexpr int vx[] = {1, 0, -1, 0}, vy[] = {0, 1, 0, -1};
constexpr long double PI = abs(acos(-1));
constexpr int sqrtN = 512, logN = 32;
constexpr long long LINF=1e18;

long long n, k, dp[2010][2010] = {};
vector<int> vec;

int main(){
	cin >> n >> k; vec.resize(n);
	for(int i = 0; i < n; i++) cin >> vec[i];
	for(int i = 0; i <= n; i++)
		for(int j = 0; j <= n; j++)
			dp[i][j] = INF;
	dp[1][0] = 0; dp[1][1] = 1;
	
	long long S = vec[0];
	for(int i = 1; i < n; i++){
		for(int j = 1; j <= i + 2; j++){
			dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]);
			
			long long X = LINF;
			long long A = dp[i][j] * vec[i];
			long long B = S;
			
			if(B) X = A / B + 1;
			if(dp[i][j] + X <= k and dp[i][j] + X <= S + vec[i]) dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] + X);
		}
		
		S += vec[i];
	}
	
	int ans = 0;
	for(int i = 1; i <= n; i++){
		if(dp[n][i] <= k) ans = i;
	}
	
	if(S == k) ans = 1;
	cout << ans << endl;
	return 0;
}

Submission Info

Submission Time
Task B - 高橋君ゲーム
User ecasdqina
Language C++14 (GCC 5.4.1)
Score 100
Code Size 2340 Byte
Status
Exec Time 39 ms
Memory 31744 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 s1.txt, s2.txt, s3.txt, s4.txt
All 100 / 100 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, 49.txt, 50.txt, 51.txt, 52.txt, 53.txt, 54.txt, 55.txt, 56.txt, 57.txt, 58.txt, 59.txt, 60.txt, 61.txt, 62.txt, 63.txt, 64.txt, s1.txt, s2.txt, s3.txt, s4.txt
Case Name Status Exec Time Memory
01.txt 39 ms 31616 KB
02.txt 37 ms 31616 KB
03.txt 35 ms 31616 KB
04.txt 39 ms 31616 KB
05.txt 35 ms 31616 KB
06.txt 39 ms 31616 KB
07.txt 39 ms 31616 KB
08.txt 39 ms 31616 KB
09.txt 39 ms 31616 KB
10.txt 35 ms 31616 KB
11.txt 38 ms 31616 KB
12.txt 39 ms 31616 KB
13.txt 37 ms 31616 KB
14.txt 39 ms 31616 KB
15.txt 37 ms 31744 KB
16.txt 39 ms 31616 KB
17.txt 39 ms 31744 KB
18.txt 38 ms 31616 KB
19.txt 39 ms 31616 KB
20.txt 35 ms 31616 KB
21.txt 39 ms 31616 KB
22.txt 39 ms 31616 KB
23.txt 39 ms 31616 KB
24.txt 39 ms 31616 KB
25.txt 39 ms 31616 KB
26.txt 39 ms 31616 KB
27.txt 39 ms 31616 KB
28.txt 39 ms 31616 KB
29.txt 36 ms 31616 KB
30.txt 38 ms 31616 KB
31.txt 38 ms 31744 KB
32.txt 39 ms 31616 KB
33.txt 38 ms 31616 KB
34.txt 35 ms 31616 KB
35.txt 39 ms 31616 KB
36.txt 38 ms 31616 KB
37.txt 39 ms 31616 KB
38.txt 36 ms 31616 KB
39.txt 38 ms 31616 KB
40.txt 35 ms 31616 KB
41.txt 38 ms 31616 KB
42.txt 39 ms 31616 KB
43.txt 37 ms 31616 KB
44.txt 39 ms 31616 KB
45.txt 38 ms 31616 KB
46.txt 39 ms 31616 KB
47.txt 35 ms 31616 KB
48.txt 35 ms 31616 KB
49.txt 35 ms 31616 KB
50.txt 35 ms 31616 KB
51.txt 1 ms 256 KB
52.txt 1 ms 256 KB
53.txt 1 ms 256 KB
54.txt 1 ms 256 KB
55.txt 1 ms 256 KB
56.txt 1 ms 256 KB
57.txt 1 ms 256 KB
58.txt 1 ms 256 KB
59.txt 1 ms 256 KB
60.txt 1 ms 256 KB
61.txt 1 ms 256 KB
62.txt 1 ms 256 KB
63.txt 1 ms 256 KB
64.txt 1 ms 256 KB
s1.txt 1 ms 256 KB
s2.txt 1 ms 256 KB
s3.txt 1 ms 256 KB
s4.txt 1 ms 256 KB