fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define Samurai ios_base::sync_with_stdio(false), cout.tie(NULL), cin.tie(NULL);
  4. string s; vector<vector<int>>dp;
  5. bool rec(int i=0, int sum = 0){
  6.     if(i == s.size()) return (sum%9 == 0);
  7.     int &ret = dp[i][sum];
  8.     if(~ret) return ret;
  9.     ret = 0;
  10.     int x = s[i] - '0';
  11.     ret |= rec(i+1,(sum+x)%9);
  12.     if(x*x < 10) ret |= rec(i+1, (sum+x*x)%9);
  13.     return ret;
  14. }
  15. int main(){ Samurai
  16.     int _t = 1;
  17.     cin >> _t;
  18.     for (int i = 1; i <= _t; i++){
  19.         cin >> s;
  20.         dp = vector<vector<int>>(s.size()+5,vector<int>(9,-1));
  21.         cout << (rec()?"YES":"NO") << '\n';
  22.     }
  23.     return 0;
  24. }
  25.  
  26.  
Success #stdin #stdout 0.01s 5248KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
YES
https://ideone.com/vjaZzE
language:
C++ (gcc 8.3)
created:
19 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!