oj.uz

답안 #833863

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
833863 2023-08-22T09:10:29 Z penguinman 비스킷 담기 (IOI20_biscuits) C++17
100 / 100
 11 ms 1316 KB 
#include "biscuits.h"
#include <bits/stdc++.h>

#ifndef EVAL
#include "grader.cpp"
#endif

using ll = long long;
using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::string;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;

#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define ln "\n"
#define pb emplace_back
#define mp std::make_pair
#define mtp std::make_tuple
#define all(a) a.begin(), a.end()

constexpr ll inf = (1ll<<60);

ll subtask_1_2_3(ll x, vi a){
	ll k = a.size();
	while(k <= 60){
		a.pb(0);
		k++;
	}
	//assert(x <= 10000);
	vi remain(1,0), val(1,1);
	rep(i,0,k){
		vector<pii> data;
		rep(j,0,remain.size()){
			data.pb(mp((remain[j]+a[i])/2, val[j]));
			if(remain[j]+a[i] >= x){
				data.pb(mp((remain[j]+a[i]-x)/2, val[j]));
			}
		}
		sort(all(data));
		remain.clear();
		val.clear();
		remain.pb(data[0].first);
		val.pb(0);
		for(auto el: data){
			if(el.first == remain.back()) val[val.size()-1] += el.second;
			else{
				remain.pb(el.first);
				val.pb(el.second);
			}
		}
	}
	ll ans = 0;
	for(auto el: val) ans += el;
	return ans;
}



long long count_tastiness(long long x, std::vector<long long> a) {
	//if(x <= 10000) return subtask_1_2_3(x,a);
	ll k = a.size();
	while(k <= 60){
		a.pb(0);
		k++;
	}
	vi sum(k);
	rep(i,0,k){
		if(i) sum[i] = sum[i-1];
		sum[i] += (1ll<<i)*a[i];
	}
	vi dp(k);
	vi require(k);
	rep(i,0,k){
		if(sum[i]/(1ll<<i) < x){
			require[i] = -1;
			continue;
		}
		else{
			require[i] = (sum[i]-(1ll<<i)*x)/x;
		}
	}
	per(i,k-1,0){
		if(require[i] == -1) continue;
		//cout << i << " "<< require[i] << ln;
		dp[i]++;
		/*if(require[i] >= (1ll<<i)){
			rep(j,0,i){
				if(require[j] != -1) dp[j] += dp[i];
			}
			continue;
		}*/
		ll cnt = 0;
		per(j,i-1,0){
			if(require[j] != -1){
				dp[j] += cnt*dp[i];
			}
			if(require[i] >= (1ll<<j)){
				if(require[j] == -1){
					rep(k,0,j){
						if(require[k] != -1){
							dp[k] += (cnt+1)*dp[i];
						}
					}
					break;
				}
				require[i] -= (1ll<<j);
				if(require[i] >= require[j]){
					dp[j] += dp[i];
					rep(k,0,j){
						if(require[k] != -1){
							dp[k] += (cnt+1)*dp[i];
						}
					}
					break;
				}
				cnt++;
			}
		}
		dp[i] *= (cnt+1);
	}
	ll ans = 1;
	rep(i,0,k){
		if(require[i] == -1) continue;
		//cout << i << " " << dp[i] << ln;
		ans += dp[i];
	}
	return ans;
}

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct

Subtask #3
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct

Subtask #4
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 7 ms 1108 KB Output is correct
3 Correct 9 ms 1108 KB Output is correct
4 Correct 7 ms 1108 KB Output is correct
5 Correct 8 ms 1108 KB Output is correct
6 Correct 7 ms 1108 KB Output is correct
7 Correct 7 ms 1108 KB Output is correct
8 Correct 7 ms 1108 KB Output is correct
9 Correct 7 ms 1108 KB Output is correct
10 Correct 6 ms 1108 KB Output is correct

Subtask #5
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 0 ms 212 KB Output is correct
27 Correct 0 ms 212 KB Output is correct
28 Correct 0 ms 212 KB Output is correct
29 Correct 1 ms 212 KB Output is correct
30 Correct 1 ms 212 KB Output is correct
31 Correct 1 ms 212 KB Output is correct
32 Correct 0 ms 212 KB Output is correct
33 Correct 1 ms 212 KB Output is correct
34 Correct 1 ms 212 KB Output is correct
35 Correct 1 ms 212 KB Output is correct
36 Correct 1 ms 212 KB Output is correct
37 Correct 2 ms 340 KB Output is correct
38 Correct 7 ms 1108 KB Output is correct
39 Correct 9 ms 1108 KB Output is correct
40 Correct 7 ms 1108 KB Output is correct
41 Correct 8 ms 1108 KB Output is correct
42 Correct 7 ms 1108 KB Output is correct
43 Correct 7 ms 1108 KB Output is correct
44 Correct 7 ms 1108 KB Output is correct
45 Correct 7 ms 1108 KB Output is correct
46 Correct 6 ms 1108 KB Output is correct
47 Correct 3 ms 340 KB Output is correct
48 Correct 9 ms 1316 KB Output is correct
49 Correct 5 ms 340 KB Output is correct
50 Correct 8 ms 1108 KB Output is correct
51 Correct 7 ms 1236 KB Output is correct
52 Correct 2 ms 340 KB Output is correct
53 Correct 6 ms 1108 KB Output is correct
54 Correct 9 ms 1108 KB Output is correct
55 Correct 11 ms 1108 KB Output is correct
56 Correct 8 ms 1108 KB Output is correct
57 Correct 8 ms 1108 KB Output is correct