fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. inline int P_th_power(int N, int M, int P) {
  5. 	using ivector = vector<int>;
  6. 	using imatrix = vector<ivector>;
  7. 	struct dp_tensor: array<imatrix,2> {
  8. 		struct powers: ivector {
  9.     		inline powers(const int p) {
  10.     			long long y, inf = 1e9;
  11.         		for (int a = 0; y = pow(a,p), y < inf; ++a)
  12.             		push_back(y); } 
  13. 			inline void generate(const int N, imatrix &dp) const {
  14.     			const int M = 1e5, null = -1;
  15.     			dp.resize(N+1,ivector(M+1,null)), dp[0][0] = 0;
  16.     			for (int n = 0; n <= N; ++n)
  17.     				for (int m = 0; m <= M; ++m)
  18.     					if (dp[n][m] != null)
  19.             				for (int a = 1, b = n+1; b <= N; ++a, ++b) {
  20.             					const int c = m+at(a);
  21.             					if (c <= M) {
  22.             						const int ans = dp[b][c], k = dp[n][m]+1;
  23.             						if (ans == null or k < ans)
  24.             							dp[b][c] = k; }
  25.             					else 
  26.             						break; } } };
  27.     	inline dp_tensor() { 
  28.     		powers(2).generate(100,at(0));
  29.     		powers(3).generate( 40,at(1)); } };
  30.     static const dp_tensor dp;
  31.     return dp[P-2][N][M]; }
  32.  
  33. int main() {
  34.     cin.tie(nullptr)->sync_with_stdio(false);
  35.     cin.exceptions(cin.failbit);
  36.     int T; cin >> T;
  37.     for(int N, M, P; T--; cout << P_th_power(N,M,P) << '\n')
  38.         cin >> N >> M >> P;
  39.     return 0; }
  40.  
Success #stdin #stdout 0.05s 59472KB
comments (?)
stdin
copy 
3
3 5 2
4 10 3
3 1 2
stdout
copy 
2
3
-1
https://ideone.com/Ueudri
Smallest positive integer - NOKIA COLLEGIATE Wilderness Coding 2022
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
secret

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!