Submission #843050

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
843050	2023-09-03 15:19:38	nonono	Soccer Stadium (IOI23_soccer)	C++17	35.50 / 100	1545 ms	584460 KiB

soccer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN = 2000;
map<int, int> dp[mxN][mxN];
int full(int N, vector<vector<int>> F) {
    vector<vector<int>> sum(N, vector<int> (N, 0));
    for(int i = 0; i < N; i ++) {
        for(int j = 0; j < N; j ++) {
            sum[i][j] = F[i][j];
            
            if(i) sum[i][j] += sum[i - 1][j];
            if(j) sum[i][j] += sum[i][j - 1];
            if(i && j) sum[i][j] -= sum[i - 1][j - 1]; 
            
        }
    }
    
    auto Area = [&] (int x, int y, int u, int v) {
        return sum[u][v] - (x ? sum[x - 1][v] : 0) - (y ? sum[u][y - 1] : 0) + (x && y ? sum[x - 1][y - 1] : 0);
    };
    
    auto Range = [&] (int x, int L, int R) {
        int low = x, high = x - 1;
        for(int i = 10; i >= 0; i --) {
            if(low - (1 << i) >= 0 && Area(low - (1 << i), L, x, R) == 0) low -= (1 << i);
            if(high + (1 << i) < N && Area(x, L, high + (1 << i), R) == 0) high += (1 << i);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 5.5 / 22
• Subtask 4: 4.5 / 18
• Subtask 5: 4 / 16
• Subtask 6: 7.5 / 30