CSES - HIIT Open 2024 - Results
Submission details
Task:Equilateral numbers
Sender:Vaicode
Submission time:2024-11-16 16:56:24 +0200
Language:C++ (C++20)
Status:READY
Result:
Test results
testverdicttime
#1ACCEPTED0.55 sdetails
#20.54 sdetails
#3ACCEPTED0.54 sdetails
#40.55 sdetails
#50.54 sdetails
#6ACCEPTED0.59 sdetails
#7ACCEPTED0.54 sdetails
#80.94 sdetails
#9--details
#10--details
#11--details
#12--details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:19:8: warning: unused variable 'm' [-Wunused-variable]
   19 |     ll m = 0;
      |        ^

Code

#include<iostream>
#include<vector>
#include <cmath>
#include <map>
using namespace std;
typedef long long ll;
#define lim 101010
int dp[lim];
map<ll, int> ek;
ll e(ll k){
return k*(k+1)/2;
}
int main()
{
ll m = 0;
dp[0] = 0;
for(ll i = 1; i< lim; ++i){
ek[e(i)] = 1;
dp[i] = 1000;
for (ll j =0; e(j) <= i; j++) {
dp[i] = min(dp[i-e(j)] + 1, dp[i]);
}
// m = max(dp[i], m);
}
ll n;
cin >> n;
int res = 100;
for(ll i = 1; i< 1000; ++i){
for(ll j = 1; j< 1000; ++j){
ek[e(i) + e(j)] = 2;
if(n - e(i) - e(j) < lim && n - e(i) - e(j) >= 0){
res = min(res, dp[n-e(i) - e(j)]+1);
}
}
}
for(ll i = 1; e(i) <= n; ++i){
if(e(i) == n){
cout << "1\n";
return 0;
}
if(ek[n - e(i)]){
res = min(res, ek[n-e(i)]+1);
}
if(n - e(i) < lim){
res = min(res, dp[n-e(i)]+1);
}
}
cout << res << endl;
}

Test details

Test 1

Verdict: ACCEPTED

input
1

correct output
1

user output
1

Test 2

Verdict:

input
2

correct output
2

user output
1

Test 3

Verdict: ACCEPTED

input
3

correct output
1

user output
1

Test 4

Verdict:

input
5

correct output
3

user output
2

Test 5

Verdict:

input
33

correct output
3

user output
2

Test 6

Verdict: ACCEPTED

input
12385719843

correct output
3

user output
3

Test 7

Verdict: ACCEPTED

input
10935032

correct output
3

user output
3

Test 8

Verdict:

input
659023495928

correct output
3

user output
100

Test 9

Verdict:

input
913591235689

correct output
2

user output
(empty)

Test 10

Verdict:

input
999999911791

correct output
1

user output
(empty)

Test 11

Verdict:

input
1000000000000

correct output
2

user output
(empty)

Test 12

Verdict:

input
999999999998

correct output
3

user output
(empty)