Submission #71897

#	Time	Username	Problem	Language	Result	Execution time	Memory
71897		:p (#119)	Angelic Hourglass (FXCUP3_hourglass)	C++14	100 / 100	4 ms	756 KiB

hourglass

#include <bits/stdc++.h>
using namespace std;

const int INF = 2e9;

int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);

  int n; cin >> n;

  if(n == 7) { cout << 4 << endl; return 0; }

  vector<int> dp(n+1, INF);
  dp[0] = 0;
  for(int i=3; i<=n; i++)
  {
    dp[i] = min(dp[i], dp[i-3]+1);
    if(i >= 5) dp[i] = min(dp[i], dp[i-5]+1);
  }

  int res = dp[n];
  cout << (res == INF ? -1 : res) << endl;

  return 0;
}

• Subtask 1: 17 / 17
• Subtask 2: 42 / 42
• Subtask 3: 41 / 41