Submission #993451


Source Code Expand

#include <bits/stdc++.h>

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

using namespace std;

template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}

using ll=long long;
const ll inf=1LL<<50;

// Problem Specific Parameter:

vector<ll> ary;
ll dp[1000010];

int main(void){
	ll n,a;
	cin >> n >> a;

	/*
	for(ll i=1;i*i<=n;++i){
		if(n%i) continue;
		ary.push_back(i);
		if(i!=n/i) ary.push_back(n/i);
	}

	dp[0]=0LL;
	const int m=ary.size();
	
	rep(i,1,m){
		dp[i]=inf;
		rep(j,i){
			if(ary[i]%ary[j]) continue;
			chmin(dp[i],dp[j]+ary[i]/ary[j]+a);	
		}
	}
	
	ll ans=n;
	rep(i,m) chmin(ans,dp[i]+(n+ary[i]-1)/ary[i]);
	cout << ans << endl;
	*/
	
	if(n>1000000) return 1;

	dp[1]=0LL;
	rep(i,2,n+1){
		dp[i]=inf;
		for(ll j=1;j*j<=i;++j){
			if(i%j) continue;
			int cur=j,nxt=i;
			chmin(dp[nxt],dp[cur]+nxt/cur+a);
			chmin(dp[nxt],dp[nxt/cur]+cur+a);
		}
	}


	ll ans=n;
	rep(i,1,n+1) chmin(ans,dp[i]+(n+i-1)/i);
	rep(i,1,n+1) cout << i << " " << dp[i]+(n+i-1)/i << endl;
	cout << ans << endl;
	

	return 0;
}

Submission Info

Submission Time
Task E - Cookies
User Hec
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1784 Byte
Status WA
Exec Time 2102 ms
Memory 3840 KB

Judge Result

Set Name sample dataset1 dataset2
Score / Max Score 0 / 0 0 / 500 0 / 500
Status
WA × 2
RE × 1
WA × 11
TLE × 16
WA × 13
TLE × 16
RE × 40
Set Name Test Cases
sample sample-01.txt, sample-02.txt, sample-03.txt
dataset1 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 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 TLE 2102 ms 3712 KB
01-02.txt TLE 2102 ms 3712 KB
01-03.txt TLE 2102 ms 3712 KB
01-04.txt TLE 2102 ms 3712 KB
01-05.txt TLE 2102 ms 3712 KB
01-06.txt TLE 2102 ms 3712 KB
01-07.txt TLE 2102 ms 3712 KB
01-08.txt TLE 2102 ms 3712 KB
01-09.txt TLE 2102 ms 3712 KB
01-10.txt TLE 2102 ms 3712 KB
01-11.txt TLE 2102 ms 3712 KB
01-12.txt TLE 2102 ms 3840 KB
01-13.txt TLE 2102 ms 3712 KB
01-14.txt WA 353 ms 1280 KB
01-15.txt TLE 2102 ms 3712 KB
01-16.txt TLE 2102 ms 3712 KB
01-17.txt TLE 2102 ms 3712 KB
01-18.txt WA 3 ms 256 KB
01-19.txt WA 3 ms 256 KB
01-20.txt WA 3 ms 256 KB
01-21.txt WA 3 ms 384 KB
01-22.txt WA 3 ms 256 KB
01-23.txt WA 3 ms 256 KB
01-24.txt WA 3 ms 256 KB
01-25.txt WA 3 ms 256 KB
01-26.txt WA 3 ms 256 KB
02-01.txt WA 3 ms 256 KB
02-02.txt RE 2 ms 256 KB
02-03.txt RE 2 ms 256 KB
02-04.txt RE 2 ms 256 KB
02-05.txt RE 2 ms 256 KB
02-06.txt RE 2 ms 256 KB
02-07.txt RE 2 ms 256 KB
02-08.txt RE 3 ms 256 KB
02-09.txt RE 2 ms 256 KB
02-10.txt RE 3 ms 256 KB
02-11.txt RE 2 ms 256 KB
02-12.txt RE 2 ms 256 KB
02-13.txt RE 3 ms 256 KB
02-14.txt RE 2 ms 256 KB
02-15.txt RE 2 ms 256 KB
02-16.txt RE 3 ms 256 KB
02-17.txt RE 2 ms 256 KB
02-18.txt RE 3 ms 256 KB
02-19.txt RE 2 ms 256 KB
02-20.txt RE 2 ms 256 KB
02-21.txt RE 2 ms 256 KB
02-22.txt RE 3 ms 256 KB
02-23.txt RE 2 ms 256 KB
02-24.txt RE 3 ms 256 KB
02-25.txt RE 2 ms 256 KB
02-26.txt RE 3 ms 256 KB
02-27.txt RE 2 ms 256 KB
02-28.txt RE 2 ms 256 KB
02-29.txt RE 2 ms 256 KB
02-30.txt RE 2 ms 256 KB
02-31.txt RE 2 ms 256 KB
02-32.txt RE 2 ms 256 KB
02-33.txt RE 2 ms 256 KB
02-34.txt RE 2 ms 256 KB
02-35.txt RE 2 ms 256 KB
02-36.txt RE 2 ms 256 KB
02-37.txt RE 3 ms 256 KB
02-38.txt RE 2 ms 256 KB
02-39.txt RE 2 ms 256 KB
02-40.txt RE 2 ms 256 KB
sample-01.txt WA 3 ms 384 KB
sample-02.txt RE 3 ms 256 KB
sample-03.txt WA 852 ms 2560 KB