Submission
# | When | Author | Problem | Language | CPU | Memory | |
---|---|---|---|---|---|---|---|
20829 | 2024-06-09 09:06:37 | AHAMMED_99 | Major Emrul & A Dream War | C | 138 ms | 5492 kb | Accepted |
Source Code
#include <stdio.h> #include <limits.h> #define MAX_LEVELS 10005 #define MAX_DRONES 105 int dp[MAX_DRONES][MAX_LEVELS]; int min(int a, int b) { return a < b ? a : b; } int max(int a, int b) { return a > b ? a : b; } int main() { int K, N; // Initialize the dp array for (int i = 0; i <= K; i++) { for (int j = 0; j <= N; j++) { dp[i][j] = INT_MAX; } } // Base cases for (int i = 1; i <= K; i++) { dp[i][0] = 0; // No levels to test dp[i][1] = 1; // Only one level to test } for (int j = 1; j <= N; j++) { dp[1][j] = j; // With one drone, we need to test each level } // Fill the dp table for (int i = 2; i <= K; i++) { for (int j = 2; j <= N; j++) { int low = 1, high = j, result = INT_MAX; while (low <= high) { int mid = (low + high) / 2; int broken = dp[i - 1][mid - 1]; // Drone breaks int not_broken = dp[i][j - mid]; // Drone does not break result = min(result, 1 + max(broken, not_broken)); if (broken > not_broken) { high = mid - 1; } else { low = mid + 1; } } dp[i][j] = result; } } int result = dp[K][N]; if (result == INT_MAX) { } else { } return 0; }