oj.uz

Submission #538802

# Submission time Handle Problem Language Result Execution time Memory
538802 2022-03-17T18:38:46 Z beaconmc Quality Of Living (IOI10_quality) C++14
80 / 100
 5000 ms 141236 KB 
#include <bits/stdc++.h>
typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
using namespace std;

#define ll int

ll pos[10000000][2];
ll pref[3001][3001];
ll r, c, h, w;

bool check(ll x){
    FOR(i,0,3001){
        FOR(j,0,3001){
            pref[i][j] = 0;
        }
    }
    FOR(i,1,x+1){
        ll a = pos[i][0];
        ll b = pos[i][1];
        pref[a+1][b+1] += 1;
        pref[max(0, a+1-h)][b+1] -= 1;
        pref[a+1][max(0, b+1-w)] -= 1;
        pref[max(0, a+1-h)][max(0, b+1-w)] += 1;
    }

    FOR(i,0,3001){
        FOR(j,1,3001){
            pref[j][i] += pref[j-1][i];
        }
    }
    FOR(i,0,3001){
        FOR(j,1,3001){
            pref[i][j] += pref[i][j-1];
        }
    }
    FOR(i,0,3001){
        FOR(j,0,3001){
            if (pref[i][j] > (h*w)/2){
                return true;
            }
        }
    }
    return false;
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
    r = R; c = C; h = H; w = W;
    FOR(i,0,R){
        FOR(j,0,C){
            pos[Q[i][j]][0] = i;
            pos[Q[i][j]][1] = j;
        }
    }
 
    int lo = 0;
    int hi = int(R*C/2)+1;
    while (lo < hi) {
		int mid = lo + (hi - lo) / 2;
		if (check(mid)) {
			hi = mid;
		} else {
			lo = mid + 1;
		}
	}
	return lo;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1076 ms 35668 KB Output is correct
2 Correct 963 ms 35668 KB Output is correct
3 Correct 1074 ms 35668 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1076 ms 35668 KB Output is correct
2 Correct 963 ms 35668 KB Output is correct
3 Correct 1074 ms 35668 KB Output is correct
4 Correct 1558 ms 36172 KB Output is correct
5 Correct 1430 ms 36052 KB Output is correct
6 Correct 1449 ms 36068 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1076 ms 35668 KB Output is correct
2 Correct 963 ms 35668 KB Output is correct
3 Correct 1074 ms 35668 KB Output is correct
4 Correct 1558 ms 36172 KB Output is correct
5 Correct 1430 ms 36052 KB Output is correct
6 Correct 1449 ms 36068 KB Output is correct
7 Correct 1904 ms 37796 KB Output is correct
8 Correct 1799 ms 37836 KB Output is correct
9 Correct 1903 ms 37688 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1076 ms 35668 KB Output is correct
2 Correct 963 ms 35668 KB Output is correct
3 Correct 1074 ms 35668 KB Output is correct
4 Correct 1558 ms 36172 KB Output is correct
5 Correct 1430 ms 36052 KB Output is correct
6 Correct 1449 ms 36068 KB Output is correct
7 Correct 1904 ms 37796 KB Output is correct
8 Correct 1799 ms 37836 KB Output is correct
9 Correct 1903 ms 37688 KB Output is correct
10 Correct 2472 ms 51288 KB Output is correct
11 Correct 2447 ms 51292 KB Output is correct
12 Correct 2226 ms 45400 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1076 ms 35668 KB Output is correct
2 Correct 963 ms 35668 KB Output is correct
3 Correct 1074 ms 35668 KB Output is correct
4 Correct 1558 ms 36172 KB Output is correct
5 Correct 1430 ms 36052 KB Output is correct
6 Correct 1449 ms 36068 KB Output is correct
7 Correct 1904 ms 37796 KB Output is correct
8 Correct 1799 ms 37836 KB Output is correct
9 Correct 1903 ms 37688 KB Output is correct
10 Correct 2472 ms 51288 KB Output is correct
11 Correct 2447 ms 51292 KB Output is correct
12 Correct 2226 ms 45400 KB Output is correct
13 Execution timed out 5091 ms 141236 KB Time limit exceeded
14 Halted 0 ms 0 KB -