Submission #1267085

#TimeUsernameProblemLanguageResultExecution timeMemory
1267085somefolkQuality Of Living (IOI10_quality)C++20
100 / 100
1456 ms71020 KiB
#include <iostream> #include <cmath> #include <algorithm> #include <string> #include <vector> #include <map> #include <unordered_map> #include <queue> #include <deque> #include <set> #include <unordered_set> #include <complex> #include <list> #include <cassert> #include <chrono> #include <random> #include <stack> #include <iomanip> #include <fstream> #include "quality.h" using namespace std; #define endl "\n" // #define int long long const int INF = 1e9+7; const int MOD = 1e9+7; int rectangle(int n, int m, int h, int w, int a[3001][3001]){ auto check = [&](int K){ vector<vector<int>> pref(n+1, vector<int>(m+1, 0)); for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ pref[i][j] = pref[i-1][j] + pref[i][j-1] - pref[i-1][j-1]; pref[i][j] += (a[i-1][j-1] <= K ? 1 : -1); } } for(int i = h; i <= n; i++){ for(int j = w; j <= m; j++){ int sum = pref[i][j] - pref[i-h][j] - pref[i][j-w] + pref[i-h][j-w]; if(sum > 0){ return true; } } } return false; }; int l = 1, r = n*m, sol = -1; while(l <= r){ int mid = (l+r)/2; if(check(mid)){ sol = mid; r = mid-1; } else { l = mid+1; } } return sol; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...