QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#824360#9778. Brotatoucup-team159#AC ✓1315ms9596kbC++203.6kb2024-12-21 13:49:042024-12-21 13:49:05

Judging History

你现在查看的是最新测评结果

  • [2024-12-21 13:49:05]
  • 评测
  • 测评结果:AC
  • 用时:1315ms
  • 内存:9596kb
  • [2024-12-21 13:49:04]
  • 提交

answer

#line 1 "K.cpp"
// #pragma GCC target("avx2,avx512f,avx512vl,avx512bw,avx512dq,avx512cd,avx512vbmi,avx512vbmi2,avx512vpopcntdq,avx512bitalg,bmi,bmi2,lzcnt,popcnt")
// #pragma GCC optimize("Ofast")

#line 2 "/home/sigma/comp/library/template.hpp"

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using uint = unsigned int;
using ull = unsigned long long;
#define rep(i,n) for(int i=0;i<int(n);i++)
#define rep1(i,n) for(int i=1;i<=int(n);i++)
#define per(i,n) for(int i=int(n)-1;i>=0;i--)
#define per1(i,n) for(int i=int(n);i>0;i--)
#define all(c) c.begin(),c.end()
#define si(x) int(x.size())
#define pb push_back
#define eb emplace_back
#define fs first
#define sc second
template<class T> using V = vector<T>;
template<class T> using VV = vector<vector<T>>;
template<class T,class U> bool chmax(T& x, U y){
	if(x<y){ x=y; return true; }
	return false;
}
template<class T,class U> bool chmin(T& x, U y){
	if(y<x){ x=y; return true; }
	return false;
}
template<class T> void mkuni(V<T>& v){sort(all(v));v.erase(unique(all(v)),v.end());}
template<class T> int lwb(const V<T>& v, const T& a){return lower_bound(all(v),a) - v.begin();}
template<class T>
V<T> Vec(size_t a) {
    return V<T>(a);
}
template<class T, class... Ts>
auto Vec(size_t a, Ts... ts) {
  return V<decltype(Vec<T>(ts...))>(a, Vec<T>(ts...));
}
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
	return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
	o<<"{";
	for(const T& v:vc) o<<v<<",";
	o<<"}";
	return o;
}
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

#ifdef LOCAL
#define show(x) cerr << "LINE" << __LINE__ << " : " << #x << " = " << (x) << endl
void dmpr(ostream& os){os<<endl;}
template<class T,class... Args>
void dmpr(ostream&os,const T&t,const Args&... args){
	os<<t<<" ~ ";
	dmpr(os,args...);
}
#define shows(...) cerr << "LINE" << __LINE__ << " : ";dmpr(cerr,##__VA_ARGS__)
#define dump(x) cerr << "LINE" << __LINE__ << " : " << #x << " = {";  \
	for(auto v: x) cerr << v << ","; cerr << "}" << endl;
#else
#define show(x) void(0)
#define dump(x) void(0)
#define shows(...) void(0)
#endif

template<class D> D divFloor(D a, D b){
	return a / b - (((a ^ b) < 0 && a % b != 0) ? 1 : 0);
}
template<class D> D divCeil(D a, D b) {
	return a / b + (((a ^ b) > 0 && a % b != 0) ? 1 : 0);
}
#line 5 "K.cpp"

using D = long double;
using P = pair<D,D>;
P operator+(const P& a, const P& b){return {a.first+b.first,a.second+b.second};}
P operator*(D a, const P& b){return {a*b.first,a*b.second};}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);		//DON'T USE scanf/printf/puts !!
	cout << fixed << setprecision(20);

	int N,K; cin >> N >> K;
	D p; cin >> p;
	chmin(K, 10000000/N);
	V<D> prev(N+1);
	V<D> tmp(N+1);
	V<P> dp(N+1);	// a+bX, X = dp[N]
	rep(i,K+1){
		auto doit = [&](int t, bool fill) -> int {
			// j <= t なら使う
			dp[0] = P(0,0);
			rep1(j,N){
				dp[j] = P(1,0) + p * (j <= t ? P(prev[j],0) : P(0,1)) + (1-p) * dp[j-1];
			}
			D X = dp[N].fs / (1 - dp[N].sc);
			int actual_t = 0;
			rep1(j,N){
				if(prev[j] <= X) actual_t = j;
			}

			if(fill){
				rep(j,N+1) chmin(tmp[j], dp[j].fs + dp[j].sc * X);
			}

			return actual_t;
		};

		rep(j,N+1) tmp[j] = 1e100;
		if(i == 0){
			doit(-1, true);
		}else{
			int lb = 1, ub = N+1;
			while(ub-lb > 1){
				int t = (lb+ub)/2;
				int actual_t = doit(t, false);
				if(actual_t <= t) ub = t;
				else lb = t;
			}
			doit(lb, true);
			doit(ub, true);
		}
		swap(prev, tmp);
	}
	cout << prev[N] << endl;
}

这程序好像有点Bug,我给组数据试试?

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3948kb

input:

5 0
0.5

output:

62.00000000000000000000

result:

ok found '62.000000000', expected '62.000000000', error '0.000000000'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3884kb

input:

5 1
0.5

output:

47.00000000000000000000

result:

ok found '47.000000000', expected '47.000000000', error '0.000000000'

Test #3:

score: 0
Accepted
time: 1ms
memory: 4060kb

input:

10000 0
0.002

output:

247489700306.91923014819622039795

result:

ok found '247489700306.919219971', expected '247489700298.253692627', error '0.000000000'

Test #4:

score: 0
Accepted
time: 128ms
memory: 9444kb

input:

100000 10
0.0002

output:

38767507134.42572061717510223389

result:

ok found '38767507134.425720215', expected '38767507133.232215881', error '0.000000000'

Test #5:

score: 0
Accepted
time: 0ms
memory: 9548kb

input:

100000 0
0.0002

output:

2430683127369.95719051361083984375

result:

ok found '2430683127369.957031250', expected '2430683127170.376953125', error '0.000000000'

Test #6:

score: 0
Accepted
time: 262ms
memory: 9596kb

input:

100000 20
0.0002

output:

801073272.25084402982611209154

result:

ok found '801073272.250844002', expected '801073272.231680870', error '0.000000000'

Test #7:

score: 0
Accepted
time: 519ms
memory: 9468kb

input:

100000 40
0.0002

output:

478148.71843518590145549751

result:

ok found '478148.718435186', expected '478148.718426307', error '0.000000000'

Test #8:

score: 0
Accepted
time: 56ms
memory: 9408kb

input:

99995 4
0.0001

output:

38976542.86817622462694998831

result:

ok found '38976542.868176222', expected '38976542.868175834', error '0.000000000'

Test #9:

score: 0
Accepted
time: 134ms
memory: 9480kb

input:

99995 10
0.0001

output:

3549184.59771205006518357550

result:

ok found '3549184.597712050', expected '3549184.597712017', error '0.000000000'

Test #10:

score: 0
Accepted
time: 208ms
memory: 9488kb

input:

99995 16
0.0001

output:

399507.47055674504645139677

result:

ok found '399507.470556745', expected '399507.470556742', error '0.000000000'

Test #11:

score: 0
Accepted
time: 105ms
memory: 9452kb

input:

99990 8
0.0001

output:

7773463.94793079628743726062

result:

ok found '7773463.947930796', expected '7773463.947930722', error '0.000000000'

Test #12:

score: 0
Accepted
time: 128ms
memory: 9520kb

input:

99990 10
0.0001

output:

3547428.94547233000184860430

result:

ok found '3547428.945472330', expected '3547428.945472297', error '0.000000000'

Test #13:

score: 0
Accepted
time: 154ms
memory: 9484kb

input:

99990 12
0.0001

output:

1647102.02043441075693408493

result:

ok found '1647102.020434411', expected '1647102.020434395', error '0.000000000'

Test #14:

score: 0
Accepted
time: 3ms
memory: 4244kb

input:

16664 1
0.0012

output:

257920044611.37292768061161041260

result:

ok found '257920044611.372924805', expected '257920044630.860534668', error '0.000000000'

Test #15:

score: 0
Accepted
time: 36ms
memory: 4232kb

input:

16664 21
0.0012

output:

92190688.54467950475373072550

result:

ok found '92190688.544679508', expected '92190688.544415027', error '0.000000000'

Test #16:

score: 0
Accepted
time: 73ms
memory: 4228kb

input:

16664 41
0.0012

output:

59865.09178608213365535562

result:

ok found '59865.091786082', expected '59865.091785920', error '0.000000000'

Test #17:

score: 0
Accepted
time: 10ms
memory: 4244kb

input:

16659 5
0.0003

output:

63366.26440695477215925280

result:

ok found '63366.264406955', expected '63366.264406955', error '0.000000000'

Test #18:

score: 0
Accepted
time: 22ms
memory: 4260kb

input:

16659 11
0.0003

output:

18120.91186354253278878446

result:

ok found '18120.911863543', expected '18120.911863543', error '0.000000000'

Test #19:

score: 0
Accepted
time: 33ms
memory: 4324kb

input:

16659 17
0.0003

output:

16666.55545196740557933879

result:

ok found '16666.555451967', expected '16666.555451967', error '0.000000000'

Test #20:

score: 0
Accepted
time: 18ms
memory: 4192kb

input:

16654 9
0.0001

output:

16656.07941657562629522715

result:

ok found '16656.079416576', expected '16656.079416576', error '0.000000000'

Test #21:

score: 0
Accepted
time: 22ms
memory: 4232kb

input:

16654 11
0.0001

output:

16655.67412217240140392960

result:

ok found '16655.674122172', expected '16655.674122172', error '0.000000000'

Test #22:

score: 0
Accepted
time: 25ms
memory: 4244kb

input:

16654 13
0.0001

output:

16655.66569536266710827022

result:

ok found '16655.665695363', expected '16655.665695363', error '0.000000000'

Test #23:

score: 0
Accepted
time: 0ms
memory: 4036kb

input:

2774 2
0.0072

output:

28951389307.29396068677306175232

result:

ok found '28951389307.293960571', expected '28951389306.987514496', error '0.000000000'

Test #24:

score: 0
Accepted
time: 6ms
memory: 3912kb

input:

2774 22
0.0072

output:

11312241.45063326401668746257

result:

ok found '11312241.450633263', expected '11312241.450653942', error '0.000000000'

Test #25:

score: 0
Accepted
time: 12ms
memory: 3852kb

input:

2774 42
0.0072

output:

8222.41510849809866101623

result:

ok found '8222.415108498', expected '8222.415108509', error '0.000000000'

Test #26:

score: 0
Accepted
time: 2ms
memory: 3924kb

input:

2769 6
0.0021

output:

13600.58235573161152132116

result:

ok found '13600.582355732', expected '13600.582355732', error '0.000000000'

Test #27:

score: 0
Accepted
time: 0ms
memory: 4012kb

input:

2769 12
0.0021

output:

3239.54997821112636313678

result:

ok found '3239.549978211', expected '3239.549978211', error '0.000000000'

Test #28:

score: 0
Accepted
time: 5ms
memory: 3912kb

input:

2769 18
0.0021

output:

2776.62819487524041583981

result:

ok found '2776.628194875', expected '2776.628194875', error '0.000000000'

Test #29:

score: 0
Accepted
time: 3ms
memory: 4008kb

input:

2764 10
0.0007

output:

2765.98707395508637918446

result:

ok found '2765.987073955', expected '2765.987073955', error '0.000000000'

Test #30:

score: 0
Accepted
time: 4ms
memory: 4008kb

input:

2764 12
0.0007

output:

2765.93736284997197527602

result:

ok found '2765.937362850', expected '2765.937362850', error '0.000000000'

Test #31:

score: 0
Accepted
time: 4ms
memory: 4076kb

input:

2764 14
0.0007

output:

2765.93617670347270620645

result:

ok found '2765.936176703', expected '2765.936176704', error '0.000000000'

Test #32:

score: 0
Accepted
time: 1315ms
memory: 9560kb

input:

100000 1000000000
0.0001

output:

100010.00100010005359507659

result:

ok found '100010.001000100', expected '100010.001000100', error '0.000000000'

Test #33:

score: 0
Accepted
time: 440ms
memory: 3944kb

input:

1 1000000000
0.5

output:

2.00000000000000000000

result:

ok found '2.000000000', expected '2.000000000', error '0.000000000'

Test #34:

score: 0
Accepted
time: 1ms
memory: 3728kb

input:

50 50
0.25

output:

66.73418733370452721188

result:

ok found '66.734187334', expected '66.734187334', error '0.000000000'

Test #35:

score: 0
Accepted
time: 0ms
memory: 3908kb

input:

40 100
0.5

output:

788.63312396627232125912

result:

ok found '788.633123966', expected '788.633123966', error '0.000000000'

Test #36:

score: 0
Accepted
time: 0ms
memory: 3724kb

input:

40 160
0.5

output:

80.00000025524792005016

result:

ok found '80.000000255', expected '80.000000255', error '0.000000000'

Test #37:

score: 0
Accepted
time: 0ms
memory: 3776kb

input:

40 162
0.5

output:

80.00000009823374218232

result:

ok found '80.000000098', expected '80.000000098', error '0.000000000'

Test #38:

score: 0
Accepted
time: 597ms
memory: 3880kb

input:

40 1000000000
0.5

output:

80.00000000000000000000

result:

ok found '80.000000000', expected '80.000000000', error '0.000000000'

Test #39:

score: 0
Accepted
time: 0ms
memory: 3844kb

input:

40 0
0.5000

output:

2199023255550.00000000000000000000

result:

ok found '2199023255550.000000000', expected '2199023255550.000000000', error '0.000000000'

Test #40:

score: 0
Accepted
time: 0ms
memory: 4020kb

input:

40 1
0.5000

output:

1649267441663.00000000000000000000

result:

ok found '1649267441663.000000000', expected '1649267441663.000000000', error '0.000000000'

Test #41:

score: 0
Accepted
time: 0ms
memory: 3876kb

input:

40 2
0.5000

output:

1236950581248.25000000000000000000

result:

ok found '1236950581248.250000000', expected '1236950581248.250000000', error '0.000000000'

Test #42:

score: 0
Accepted
time: 0ms
memory: 3912kb

input:

40 3
0.5000

output:

962072674305.00000000000000000000

result:

ok found '962072674305.000000000', expected '962072674305.000000000', error '0.000000000'

Test #43:

score: 0
Accepted
time: 0ms
memory: 3880kb

input:

40 4
0.5000

output:

738734374914.21875000000000000000

result:

ok found '738734374914.218750000', expected '738734374914.218750000', error '0.000000000'

Test #44:

score: 0
Accepted
time: 0ms
memory: 3784kb

input:

40 5
0.5000

output:

575525617666.95312500000000000000

result:

ok found '575525617666.953125000', expected '575525617666.953125000', error '0.000000000'

Test #45:

score: 0
Accepted
time: 0ms
memory: 3784kb

input:

40 10
0.5000

output:

173409304583.13256835937500000000

result:

ok found '173409304583.132568359', expected '173409304583.132568359', error '0.000000000'

Test #46:

score: 0
Accepted
time: 0ms
memory: 3844kb

input:

40 15
0.5000

output:

55390502923.07350826263427734375

result:

ok found '55390502923.073509216', expected '55390502923.073509216', error '0.000000000'

Test #47:

score: 0
Accepted
time: 0ms
memory: 4032kb

input:

40 20
0.5000

output:

18180087821.74740450084209442139

result:

ok found '18180087821.747406006', expected '18180087821.747406006', error '0.000000000'

Test #48:

score: 0
Accepted
time: 0ms
memory: 3780kb

input:

40 25
0.5000

output:

5963269457.31878360174596309662

result:

ok found '5963269457.318783760', expected '5963269457.318783760', error '0.000000000'

Test #49:

score: 0
Accepted
time: 0ms
memory: 3784kb

input:

40 30
0.5000

output:

2008652291.20979898096993565559

result:

ok found '2008652291.209799051', expected '2008652291.209799051', error '0.000000000'

Test #50:

score: 0
Accepted
time: 0ms
memory: 3724kb

input:

40 35
0.5000

output:

676323760.76680406328523531556

result:

ok found '676323760.766804099', expected '676323760.766804099', error '0.000000000'

Test #51:

score: 0
Accepted
time: 1ms
memory: 3848kb

input:

40 40
0.5000

output:

231036317.11780157298198901117

result:

ok found '231036317.117801577', expected '231036317.117801577', error '0.000000000'

Test #52:

score: 0
Accepted
time: 1ms
memory: 3848kb

input:

40 45
0.5000

output:

79224360.24568989693943876773

result:

ok found '79224360.245689899', expected '79224360.245689899', error '0.000000000'

Test #53:

score: 0
Accepted
time: 1ms
memory: 3948kb

input:

40 50
0.5000

output:

27134304.85083361087890807539

result:

ok found '27134304.850833610', expected '27134304.850833610', error '0.000000000'

Test #54:

score: 0
Accepted
time: 0ms
memory: 3728kb

input:

2 1
0.0001

output:

2.00020003000400050015

result:

ok found '2.000200030', expected '2.000200030', error '0.000000000'

Test #55:

score: 0
Accepted
time: 0ms
memory: 3844kb

input:

2 0
0.0001

output:

2.00030004000500060009

result:

ok found '2.000300040', expected '2.000300040', error '0.000000000'

Test #56:

score: 0
Accepted
time: 0ms
memory: 4012kb

input:

2 2
0.0001

output:

2.00020002000300040025

result:

ok found '2.000200020', expected '2.000200020', error '0.000000000'

Test #57:

score: 0
Accepted
time: 0ms
memory: 3764kb

input:

2 3
0.0001

output:

2.00020002000200030007

result:

ok found '2.000200020', expected '2.000200020', error '0.000000000'

Test #58:

score: 0
Accepted
time: 778ms
memory: 9552kb

input:

100000 60
0.0002

output:

100020.27483830506677975336

result:

ok found '100020.274838305', expected '100020.274838305', error '0.000000000'

Test #59:

score: 0
Accepted
time: 1040ms
memory: 9504kb

input:

100000 80
0.0002

output:

100020.00400080025092108826

result:

ok found '100020.004000800', expected '100020.004000800', error '0.000000000'

Test #60:

score: 0
Accepted
time: 1305ms
memory: 9560kb

input:

100000 100
0.0002

output:

100020.00400080024836313441

result:

ok found '100020.004000800', expected '100020.004000800', error '0.000000000'

Test #61:

score: 0
Accepted
time: 1303ms
memory: 9536kb

input:

100000 120
0.0002

output:

100020.00400080024836313441

result:

ok found '100020.004000800', expected '100020.004000800', error '0.000000000'

Test #62:

score: 0
Accepted
time: 1302ms
memory: 9532kb

input:

100000 140
0.0002

output:

100020.00400080024836313441

result:

ok found '100020.004000800', expected '100020.004000800', error '0.000000000'

Test #63:

score: 0
Accepted
time: 1302ms
memory: 9536kb

input:

100000 180
0.0002

output:

100020.00400080024836313441

result:

ok found '100020.004000800', expected '100020.004000800', error '0.000000000'

Test #64:

score: 0
Accepted
time: 708ms
memory: 9440kb

input:

100000 55
0.0002

output:

100070.85032820617408333419

result:

ok found '100070.850328206', expected '100070.850328203', error '0.000000000'

Test #65:

score: 0
Accepted
time: 644ms
memory: 9492kb

input:

100000 50
0.0002

output:

103207.68419321412591216358

result:

ok found '103207.684193214', expected '103207.684193091', error '0.000000000'

Extra Test:

score: 0
Extra Test Passed