Submission #1233153

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233153		santi3223	Quality Of Living (IOI10_quality)	C++20	40 / 100	686 ms	327680 KiB

quality

#include <bits/stdc++.h>
#include "quality.h"
using namespace std;
#define ll long long
#define vb vector<bool>
#define pb push_back
#define ff(aa, bb, cc) for(ll aa = bb; aa < cc; aa++)
#define vl vector<ll>
#define pll pair<ll, ll>
#define fi first
#define se second
#define ed "\n"
#define all(aaa) aaa.begin(), aaa.end()
#define rall(aaa) aaa.rbegin(), aaa.rend()
ll MOD = 1e9+7;
 

int rectangle(int r, int c, int h, int w, int Q[3001][3001]){
	vector<vector<set<ll>>> calc(r-h+1+5, vector<set<ll>>(c-w+1+5));
	vector<vl> erasi(r-h+1+5);
	vector<vector<vl>> erasj(r-h+1+5, vector<vl>(c-w+1+5));
	ff(i, 0, r-h+1){
		ff(j, 0, c-w+1){
			if(i == 0 && j == 0){
				ff(curi, i, i+h){
					ff(curj, j, j+w){
						if(curi == i){
							erasi[i].pb(Q[curi][curj]);
						}
						if(curj == j){
							erasj[i][j].pb(Q[curi][curj]);
						}
						calc[i][j].insert(Q[curi][curj]);
					}
				}
				continue;
			}
			if(j == 0){
				set<ll> cur = calc[i-1][j];
				ff(curi, 0, erasi[i-1].size()){
					cur.erase(erasi[i-1][curi]);
				}
				ff(curj, j, j+w){
					erasi[i].pb(Q[i][curj]);
				}
				ff(curj, j, j+w){
					cur.insert(Q[i+h-1][curj]);
					//erasi[i+j-1].pb(Q[i+h-1][])
				}
				ff(curi, i, i+h){
					erasj[i][j].pb(Q[curi][j]);
				}
				calc[i][j] = cur;
			}
			else{
				set<ll> cur = calc[i][j-1];
				for(auto &x : erasj[i][j-1]){
					cur.erase(x);
				}
				ff(curi, i, i+h){
					cur.insert(Q[curi][j+w-1]);
				}
				ff(curi, i, i+h){
					erasj[i][j].pb(Q[curi][j]);
				}
				calc[i][j] = cur;
			}
		}
	}
	ll minn = r*c+1;
	ff(i, 0, r-h+1){
		ff(j, 0, c-w+1){
			//cout << i << " " << j << ed;
			set<ll> st = calc[i][j];
			vl a;
			for(auto &p : st){
				//cout << p << " ";
				a.pb(p);
			}
			//cout << ed << ed;
			ll cur = a[st.size()/2];
			minn = min(minn, cur);
		}
	}
	return minn;
}
/*
static int R,C,H,W,Q[3001][3001],i,j,ans;
int main(){
   scanf("%d%d%d%d",&R,&C,&H,&W);
   for (i=0;i<R;i++) for (j=0;j<C;j++) scanf("%d",&Q[i][j]);
   ans = rectangle(R,C,H,W,Q);
   printf("%d\n",ans);
   return 0;
}
*/

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20