oj.uz

Submission #937648

# Submission time Handle Problem Language Result Execution time Memory
937648 2024-03-04T10:10:16 Z Wansur Soccer Stadium (IOI23_soccer) C++17
48 / 100
 860 ms 117972 KB 
#include <bits/stdc++.h>
#define f first
#define s second
#define ent '\n'

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")

typedef long long ll;
using namespace std;
struct seg{
    int m1,m2,sum,cnt;
};

const string out[2]={"NO\n","YES\n"};

const ll dx[]={0,1,0,-1,-1,1,1,-1};
const ll dy[]={1,0,-1,0,-1,1,-1,1};
const int mod=998244353;
const int md=1e9+7;
const int mx=2e3+12;
const bool T=0;

int dp[61][61][61][61];
bool used[2001][2001];
int pref[61][61];
int n;

int get(int i,int l,int r){
    if(!l)return pref[i][r];
    return pref[i][r]-pref[i][l-1];
}

void dfs(int x,int y){
    used[x][y]=1;
    for(int i=0;i<4;i++){
        int x1=dx[i]+x,y1=dy[i]+y;
        if(min(x1,y1)>=0 && max(x1,y1)<n && !used[x1][y1]){
            dfs(x1,y1);
        }
    }
}

int solve(int N, vector<vector<int>> a){

    int sum=0;
    n=N;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            sum+=!a[i][j];
            if(a[i][j]){
                used[i][j]=1;
            }
        }
    }
    bool ok=0;
    int pos=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(!used[i][j]){
                pos=i;
                if(ok)return 0;
                ok=1;
                dfs(i,j);
            }
        }
    }
    int l=-1,r=-1;
    int len=0,sg=0;
    vector<pair<int,int>> v;
    for(int i=pos;i<n;i++){
        int tl=-1,tr=-1,sum=0;
        for(int j=0;j<n;j++){
            if(!a[i][j]) {
                ok = 1;
                if(tl==-1){
                    tl=j;
                }
                tr=j;
                sum++;
            }
        }
        if(tl==-1)break;
        if(l==-1){
            l=tl,r=tr;
        }
        if(!(l<=tl && tr<=r || tl<=l && r<=tr) || sum!=tr-tl+1){
            return 0;
        }
        if(r-l+1 <= tr-tl+1){
            if(r-l+1 < tr-tl+1 && sg){
                return 0;
            }
        }
        else{
            sg=1;
        }
        l=tl,r=tr;
        v.push_back({tl,tr});
    }
    sort(v.begin(),v.end(),[](pair<int,int> a,pair<int,int> b){
        return a.s-a.f>b.s-b.f;
    });
    l=v[0].f,r=v[0].s;
    for(auto [tl,tr]: v){
        if(tl < l || tr > r){
            return 0;
        }
        l=tl, r=tr;
    }
    return sum;
}

int biggest_stadium(int N, vector<vector<int>> a) {
    n = N;
    if (n > 30) {

    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            pref[i][j] = a[i][j];
            if (j)pref[i][j] += pref[i][j - 1];
        }
    }
    int ans=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            for(int l=0;l<n;l++){
                for(int r=0;r<n;r++){
                    dp[i][j][l][r]=-1e9;
                }
            }
        }
    }
    for(int i=0;i<n;i++){
        for(int l=0;l<n;l++){
            for(int r=l;r<n;r++){
                if(a[i][r])break;
                ans=max(ans,r-l+1);
                dp[i][i][l][r]=r-l+1;
            }
        }
    }
    for(int len=2;len<=n;len++){
        for(int i=0;i+len-1<n;i++){
            int j=i+len-1;
            for(int len=1;len<=n;len++){
                for(int l=0;l+len-1<n;l++){
                    int r=l+len-1;
                    if(!get(i,l,r)){
                        for(int tl=l;tl>=0;tl--){
                            for(int tr=r;tr<n;tr++){
                                dp[i][j][l][r]=max(dp[i][j][l][r], dp[i+1][j][tl][tr] + r-l+1);
                            }
                        }
                    }
                    if(!get(j,l,r)){
                        for(int tl=l;tl>=0;tl--){
                            for(int tr=r;tr<n;tr++){
                                dp[i][j][l][r]=max(dp[i][j][l][r], dp[i][j-1][tl][tr] + r-l+1);
                            }
                        }
                    }
                    ans=max(ans,dp[i][j][l][r]);
                }
            }
        }
    }
    return ans;
}

Compilation message

soccer.cpp: In function 'int solve(int, std::vector<std::vector<int> >)':
soccer.cpp:87:20: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   87 |         if(!(l<=tl && tr<=r || tl<=l && r<=tr) || sum!=tr-tl+1){
      |              ~~~~~~^~~~~~~~
soccer.cpp:69:9: warning: unused variable 'len' [-Wunused-variable]
   69 |     int len=0,sg=0;
      |         ^~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB ok

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB ok
2 Correct 1 ms 4444 KB ok
3 Correct 1 ms 10588 KB ok
4 Correct 1 ms 10588 KB ok
5 Correct 1 ms 2396 KB ok
6 Correct 1 ms 4444 KB ok
7 Runtime error 68 ms 114004 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB ok
2 Correct 1 ms 4444 KB ok
3 Correct 1 ms 4444 KB ok
4 Correct 1 ms 4444 KB ok
5 Correct 1 ms 4440 KB ok
6 Correct 1 ms 4444 KB ok
7 Correct 1 ms 4444 KB ok
8 Correct 1 ms 4440 KB ok
9 Correct 1 ms 4444 KB ok
10 Correct 1 ms 4600 KB ok
11 Correct 1 ms 4444 KB ok
12 Correct 1 ms 4444 KB ok
13 Correct 1 ms 4444 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB ok
2 Correct 1 ms 4444 KB ok
3 Correct 1 ms 4444 KB ok
4 Correct 1 ms 4444 KB ok
5 Correct 1 ms 4444 KB ok
6 Correct 1 ms 4440 KB ok
7 Correct 1 ms 4444 KB ok
8 Correct 1 ms 4444 KB ok
9 Correct 1 ms 4440 KB ok
10 Correct 1 ms 4444 KB ok
11 Correct 1 ms 4600 KB ok
12 Correct 1 ms 4444 KB ok
13 Correct 1 ms 4444 KB ok
14 Correct 1 ms 4444 KB ok
15 Correct 1 ms 8540 KB ok
16 Correct 1 ms 8540 KB ok
17 Correct 1 ms 8536 KB ok
18 Correct 2 ms 8540 KB ok
19 Correct 1 ms 8540 KB ok
20 Correct 1 ms 8536 KB ok
21 Correct 2 ms 8540 KB ok
22 Correct 1 ms 8540 KB ok
23 Correct 2 ms 8536 KB ok
24 Correct 1 ms 8540 KB ok
25 Correct 1 ms 8540 KB ok
26 Correct 1 ms 8540 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB ok
2 Correct 1 ms 4444 KB ok
3 Correct 1 ms 4444 KB ok
4 Correct 1 ms 10588 KB ok
5 Correct 1 ms 10588 KB ok
6 Correct 1 ms 4444 KB ok
7 Correct 1 ms 4444 KB ok
8 Correct 1 ms 4440 KB ok
9 Correct 1 ms 4444 KB ok
10 Correct 1 ms 4444 KB ok
11 Correct 1 ms 4440 KB ok
12 Correct 1 ms 4444 KB ok
13 Correct 1 ms 4600 KB ok
14 Correct 1 ms 4444 KB ok
15 Correct 1 ms 4444 KB ok
16 Correct 1 ms 4444 KB ok
17 Correct 1 ms 8540 KB ok
18 Correct 1 ms 8540 KB ok
19 Correct 1 ms 8536 KB ok
20 Correct 2 ms 8540 KB ok
21 Correct 1 ms 8540 KB ok
22 Correct 1 ms 8536 KB ok
23 Correct 2 ms 8540 KB ok
24 Correct 1 ms 8540 KB ok
25 Correct 2 ms 8536 KB ok
26 Correct 1 ms 8540 KB ok
27 Correct 1 ms 8540 KB ok
28 Correct 1 ms 8540 KB ok
29 Correct 1 ms 8540 KB ok
30 Correct 19 ms 29180 KB ok
31 Correct 14 ms 29020 KB ok
32 Correct 8 ms 29020 KB ok
33 Correct 6 ms 29020 KB ok
34 Correct 7 ms 29020 KB ok
35 Correct 12 ms 29184 KB ok
36 Correct 6 ms 29020 KB ok
37 Correct 8 ms 29016 KB ok
38 Correct 8 ms 29020 KB ok
39 Correct 8 ms 29176 KB ok
40 Correct 27 ms 29016 KB ok
41 Correct 25 ms 29016 KB ok

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB ok
2 Correct 1 ms 4444 KB ok
3 Correct 1 ms 4444 KB ok
4 Correct 1 ms 10588 KB ok
5 Correct 1 ms 10588 KB ok
6 Correct 1 ms 4444 KB ok
7 Correct 1 ms 4444 KB ok
8 Correct 1 ms 4440 KB ok
9 Correct 1 ms 4444 KB ok
10 Correct 1 ms 4444 KB ok
11 Correct 1 ms 4440 KB ok
12 Correct 1 ms 4444 KB ok
13 Correct 1 ms 4600 KB ok
14 Correct 1 ms 4444 KB ok
15 Correct 1 ms 4444 KB ok
16 Correct 1 ms 4444 KB ok
17 Correct 1 ms 8540 KB ok
18 Correct 1 ms 8540 KB ok
19 Correct 1 ms 8536 KB ok
20 Correct 2 ms 8540 KB ok
21 Correct 1 ms 8540 KB ok
22 Correct 1 ms 8536 KB ok
23 Correct 2 ms 8540 KB ok
24 Correct 1 ms 8540 KB ok
25 Correct 2 ms 8536 KB ok
26 Correct 1 ms 8540 KB ok
27 Correct 1 ms 8540 KB ok
28 Correct 1 ms 8540 KB ok
29 Correct 1 ms 8540 KB ok
30 Correct 19 ms 29180 KB ok
31 Correct 14 ms 29020 KB ok
32 Correct 8 ms 29020 KB ok
33 Correct 6 ms 29020 KB ok
34 Correct 7 ms 29020 KB ok
35 Correct 12 ms 29184 KB ok
36 Correct 6 ms 29020 KB ok
37 Correct 8 ms 29016 KB ok
38 Correct 8 ms 29020 KB ok
39 Correct 8 ms 29176 KB ok
40 Correct 27 ms 29016 KB ok
41 Correct 25 ms 29016 KB ok
42 Runtime error 860 ms 117972 KB Execution killed with signal 11
43 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB ok
2 Correct 1 ms 4444 KB ok
3 Correct 1 ms 4444 KB ok
4 Correct 1 ms 10588 KB ok
5 Correct 1 ms 10588 KB ok
6 Correct 1 ms 2396 KB ok
7 Correct 1 ms 4444 KB ok
8 Runtime error 68 ms 114004 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -