xxxxxxxxxx
using namespace std;
constexpr ll INF = (1ll << 60);
template <typename T>
inline bool chmin(T &a, T b) {
if (a > b) {
a = b;
return 1;
}
return 0;
}
int main() {
ll n,ans=0;
cin>>n;
vll a(n+1,INF); //a[x]... x = A*B となるA+Bの最小値
//a[0]...a[N]を求める O(NlogN)
rep(i,n+1){
rep(j,n+1){
if(i*j>n) break;
chmin(a[i*j],i+j);
}
}
//累積最小値を取る O(N)
rep(i,n){
chmin(a[i+1],a[i]+1);
ans+=a[i+1];
}
cout<<ans<<endl;
}
提出日時 | |
ユーザー | ![]() |
言語 | C++ (GCC 9.3.0) |
結果 | AC |
実行時間 | 206 ms |
メモリ | 40196 kb |
テストケース名 | 結果 | 実行時間 | メモリ |
---|---|---|---|
hand01 | AC | 124 ms | 40196 kb |
hand02 | AC | 4 ms | 40196 kb |
hand03 | AC | 52 ms | 40196 kb |
hand04 | AC | 123 ms | 40196 kb |
hand05 | AC | 206 ms | 40196 kb |
hand06 | AC | 178 ms | 40196 kb |
hand07 | AC | 206 ms | 40196 kb |
random_case_1.txt | AC | 20 ms | 40196 kb |
random_case_2.txt | AC | 10 ms | 40196 kb |
random_case_3.txt | AC | 11 ms | 40196 kb |
random_case_4.txt | AC | 31 ms | 40196 kb |
random_case_5.txt | AC | 111 ms | 40196 kb |
random_case_6.txt | AC | 100 ms | 40196 kb |
sample01 | AC | 4 ms | 40196 kb |
sample02 | AC | 4 ms | 40196 kb |
sample03 | AC | 4 ms | 40196 kb |