CSES - HIIT Open 2024 - Results
Submission details
Task:Equilateral numbers
Sender:CPLX
Submission time:2024-11-16 16:31:13 +0200
Language:C++ (C++17)
Status:READY
Result:
Test results
testverdicttime
#1ACCEPTED0.00 sdetails
#2ACCEPTED0.00 sdetails
#30.00 sdetails
#4ACCEPTED0.00 sdetails
#50.00 sdetails
#60.01 sdetails
#7--details
#80.03 sdetails
#90.03 sdetails
#100.03 sdetails
#110.03 sdetails
#120.03 sdetails

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:31:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for(int i=0; i<nums.size(); i++){
      |                  ~^~~~~~~~~~~~

Code

#include <bits/stdc++.h>
#include <limits>
using namespace std;
typedef long long ll;


int main()
{

    ll n;
    cin >> n;
    vector<ll> nums;

    ll k = 1;
    ll eq = 1;
    nums.push_back(k);
    ++k;
    //cout << eq << endl;
    while (eq <= n)
    {
        eq += k;
        nums.push_back(eq);
        ++k;
        //cout << eq << endl;
    }

    vector<int> dp(n+1,-1);
    dp[1] = 1;
    dp[0] = 0;
    
    for(int i=0; i<nums.size(); i++){
        if(nums[i]<n)dp[nums[i]] = 1;
    }

    //for(int i=0; i<dp.size(); i++) cout << dp[i] << " ";
    //cout << endl;

    for(int i=1; i<(n+1); i++){
        if(dp[i]!=-1)continue;

        ll l = i-1;
        ll max = i;

        ll nops = 0;
        while (max > 0 and l >= 1)
        {

            if (l <= max)
            {
                //cout << "->>>" << l << endl;
                max -= l;

                nops += dp[l];
            }
            else
                --l;
        }
        dp[i] = nops;
        //cout << i << "------------" << endl;
    }
    cout << dp[n] << endl;
}

Test details

Test 1

Verdict: ACCEPTED

input
1

correct output
1

user output
1

Test 2

Verdict: ACCEPTED

input
2

correct output
2

user output
2

Test 3

Verdict:

input
3

correct output
1

user output
3

Test 4

Verdict: ACCEPTED

input
5

correct output
3

user output
3

Test 5

Verdict:

input
33

correct output
3

user output
6

Test 6

Verdict:

input
12385719843

correct output
3

user output
(empty)

Error:
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Test 7

Verdict:

input
10935032

correct output
3

user output
(empty)

Test 8

Verdict:

input
659023495928

correct output
3

user output
(empty)

Error:
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Test 9

Verdict:

input
913591235689

correct output
2

user output
(empty)

Error:
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Test 10

Verdict:

input
999999911791

correct output
1

user output
(empty)

Error:
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Test 11

Verdict:

input
1000000000000

correct output
2

user output
(empty)

Error:
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Test 12

Verdict:

input
999999999998

correct output
3

user output
(empty)

Error:
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc