oj.uz

Submission #383856

# Submission time Handle Problem Language Result Execution time Memory
383856 2021-03-30T22:36:17 Z MODDI Quality Of Living (IOI10_quality) C++14
40 / 100
 5000 ms 13156 KB 
#include "quality.h"
#include <bits/stdc++.h>
#define ll long long
#define	pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define mp make_pair
#define pb push_back 
using namespace std;
int matrix[3001][3001], n, m, r, c;
int arr[3001][3001];
int sum[3001][3001], mat[3001][3001];
bool solve(int fix, int fx, int fy)
{
    for(int i = 0; i < n; i++){
    	for(int j = 0; j < m; j++){
    		if(matrix[i][j] > fix)
    			mat[i][j] = 1;
    		else if(matrix[i][j] < fix)
    			mat[i][j] = -1;
    		else
    			mat[i][j]=0;
		}
	}
    sum[0][0] = mat[0][0];
    for (int j = 1; j < m; j++) {
        sum[0][j] = mat[0][j] + sum[0][j - 1];
    }
    for (int i = 1; i < n; i++) {
        sum[i][0] = mat[i][0] + sum[i - 1][0];
    }
    for (int i = 1; i < n; i++)
    {
        for (int j = 1; j < m; j++)
        {
            sum[i][j] = mat[i][j] + sum[i - 1][j] + sum[i][j - 1]
                - sum[i - 1][j - 1];
        }
    }
    int total;
    for (int i = r - 1; i < n; i++)
    {
        for (int j = c - 1; j < m; j++)
        {
            total = sum[i][j];
            if (i - r >= 0) {
                total = total - sum[i - r][j];
            }
            if (j - c >= 0) {
                total = total - sum[i][j - c];
            }
            if (i - r >= 0 && j - c >= 0) {
                total = total + sum[i -r][j - c];
            }
            if(total == 0 && fx <= i && fy <= j) {
                return true;
            }
        }
    }
    return false;
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	n = R;
	m = C;
	r = H;
	c = W;
	vi arr1;
	map<int, pii> mapa;
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++){
			matrix[i][j] = Q[i][j];
			arr1.pb(Q[i][j]);
			mapa[Q[i][j]] = mp(i,j);
		}
		
	sort(arr1.begin(), arr1.end());
	for(int i = 0; i < arr1.size(); i++){
		bool check = solve(arr1[i], mapa[arr1[i]].first, mapa[arr1[i]].second);
		if(check)
			return arr1[i];
	}
}/*
int main(){
	int a, b, c, d;
	cin>>a>>b>>c>>d;
	
	for(int i = 0; i < a; i++){
		for(int j = 0; j < b; j++)
			cin>>arr[i][j];
	}
	cout<<rectangle(a, b, c, d)<<endl;
	return 0;
}*/

Compilation message

quality.cpp: In function 'int rectangle(int, int, int, int, int (*)[3001])':
quality.cpp:78:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |  for(int i = 0; i < arr1.size(); i++){
      |                 ~~^~~~~~~~~~~~~
quality.cpp:68:5: warning: control reaches end of non-void function [-Wreturn-type]
   68 |  vi arr1;
      |     ^~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 876 KB Output is correct
2 Correct 3 ms 876 KB Output is correct
3 Correct 3 ms 876 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 876 KB Output is correct
2 Correct 3 ms 876 KB Output is correct
3 Correct 3 ms 876 KB Output is correct
4 Correct 278 ms 2796 KB Output is correct
5 Correct 272 ms 2796 KB Output is correct
6 Correct 282 ms 2924 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 876 KB Output is correct
2 Correct 3 ms 876 KB Output is correct
3 Correct 3 ms 876 KB Output is correct
4 Correct 278 ms 2796 KB Output is correct
5 Correct 272 ms 2796 KB Output is correct
6 Correct 282 ms 2924 KB Output is correct
7 Execution timed out 5042 ms 13156 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 876 KB Output is correct
2 Correct 3 ms 876 KB Output is correct
3 Correct 3 ms 876 KB Output is correct
4 Correct 278 ms 2796 KB Output is correct
5 Correct 272 ms 2796 KB Output is correct
6 Correct 282 ms 2924 KB Output is correct
7 Execution timed out 5042 ms 13156 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 876 KB Output is correct
2 Correct 3 ms 876 KB Output is correct
3 Correct 3 ms 876 KB Output is correct
4 Correct 278 ms 2796 KB Output is correct
5 Correct 272 ms 2796 KB Output is correct
6 Correct 282 ms 2924 KB Output is correct
7 Execution timed out 5042 ms 13156 KB Time limit exceeded
8 Halted 0 ms 0 KB -