UVa 10306 e-Coins Solution

#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
vector<int> x(41),y(41);
vector<vector<int> > dp(301,vector<int>(301,-1));
int n,s;
int cc(int i,int xsum,int ysum){
    if(xsum==0&&ysum==0)return 0;
    if(xsum<0||ysum<0||i==n)return 90001;
    if(dp[xsum][ysum]!=-1)return dp[xsum][ysum];
    return dp[xsum][ysum]=min(cc(i+1,xsum,ysum),1+cc(i,xsum-x[i],ysum-y[i]));
}
int main(){
    int t;
    cin>>t;
    while(t--){
       
        cin>>n>>s;
        for(auto &i:dp)
            fill(i.begin(),i.end(),-1);
        int i=0;
        vector<vector<int> > xy;
        while(i<n){
            cin>>x[i]>>y[i];
            i++;
        }
        for(int i=0;i<=s;i++){
            for(int j=s;j>=0;j--){
                if(i*i+j*j==s*s)
                    xy.push_back({i,j});
                else if(i*i+j*j<s)
                    break;
            }
        }
        int ans=90001;
        for(int i=0;i<xy.size();i++){
            ans=min(ans,cc(0,xy[i][0],xy[i][1]));
        }
        if(ans!=90001)cout<<ans<<endl;
        else cout<<"not possible"<<endl;
    }
    return 0;
}