oj.uz

Submission #1074442

# Submission time Handle Problem Language Result Execution time Memory
1074442 2024-08-25T10:33:08 Z anango Soccer Stadium (IOI23_soccer) C++17
0 / 100
 4500 ms 4696 KB 
#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;
vector<vector<int>> pref;

int INF = 1LL<<30;

int query(int a, int b, int c, int d) {
    if (a<c) swap(a,c);
    if (b<d) swap(b,d);
    return pref[c+1][d+1]-pref[a][d+1]-pref[c+1][b]+pref[a][b];
}

signed biggest_stadium(signed N, vector<vector<signed>> F) {
    //the stadium is valid iff for every pair of cells (a,b) and (c,d), 
    //everything in the paths (a,b) to (a,d) to (c,d) is inside
    //or everything in the paths (a,b) to (a,c) to (c,d) is inside
    n=N;
    pref=vector<vector<int>>(n+1,vector<int>(n+1,0));
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            pref[i+1][j+1] = pref[i+1][j]+pref[i][j+1]-pref[i][j]+F[i][j];
        }
    }
    for (int a=0; a<n; a++) {
        for (int b=0; b<n; b++) {
            for (int c=0; c<n; c++) {
                for (int d=0; d<n; d++) {
                    if (F[a][b]==1 || F[c][d]==1) continue;
                    //everything in the paths (a,b) to (a,d) to (c,d) is inside
                    if (query(a,b,a,d)==0 && query(a,d,c,d)==0) continue;
                    //or everything in the paths (a,b) to (a,c) to (c,d) is inside
                    if (query(a,b,a,c)==0 && query(a,c,c,d)==0) continue;
                    return INF;
                }
            }
        }
    }
    //cout << "jambloat " << pref[n][n] << endl;
    return n*n-pref[n][n];
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB partial

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 1 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 408 KB ok
6 Partially correct 0 ms 348 KB partial
7 Partially correct 1 ms 604 KB partial
8 Execution timed out 4546 ms 4696 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Partially correct 1 ms 344 KB partial
4 Partially correct 0 ms 344 KB partial
5 Partially correct 0 ms 348 KB partial
6 Incorrect 0 ms 348 KB wrong
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB partial
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Partially correct 1 ms 344 KB partial
5 Partially correct 0 ms 344 KB partial
6 Partially correct 0 ms 348 KB partial
7 Incorrect 0 ms 348 KB wrong
8 Halted 0 ms 0 KB -

Subtask #4
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB partial
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 1 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Partially correct 1 ms 344 KB partial
7 Partially correct 0 ms 344 KB partial
8 Partially correct 0 ms 348 KB partial
9 Incorrect 0 ms 348 KB wrong
10 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB partial
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 1 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Partially correct 1 ms 344 KB partial
7 Partially correct 0 ms 344 KB partial
8 Partially correct 0 ms 348 KB partial
9 Incorrect 0 ms 348 KB wrong
10 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB partial
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 1 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 408 KB ok
7 Partially correct 0 ms 348 KB partial
8 Partially correct 1 ms 604 KB partial
9 Execution timed out 4546 ms 4696 KB Time limit exceeded
10 Halted 0 ms 0 KB -