oj.uz

답안 #994877

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
994877 2024-06-08T07:59:32 Z 김은성(#10865) 축구 경기장 (IOI23_soccer) C++17
6 / 100
 215 ms 31768 KB 
#define SUB
#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
#ifndef SUB
int l[2009], r[2009], i;
int psumr[2009][2009], psumc[2009][2009];
bool consecutive(vector<int> vec){
    int i;
    for(i=0; i+1<vec.size(); i++){
        if(vec[i+1] != vec[i] + 1)
            return false;
    }
    return true;
}
bool bitonic(vector<int> vec){
    int i, trend = 0;
    for(i=0; i+1<vec.size(); i++){
        //printf("vec=%d %d trend=%d\n", vec[i], vec[i+1], trend);
        if(vec[i] < vec[i+1] && trend)
            return false;
        if(vec[i] > vec[i+1])
            trend = 1;
    }
    return true;
}

pair<int, int> change_trend(vector<int> vec){
    int i;
    vector<int> opt;
    int mx = -12839423;
    for(i=0; i<vec.size(); i++){
        //printf("vec[i]=%d\n", vec[i]);
        if(vec[i] > mx){
            opt.clear();
            opt.push_back(i);
            mx = vec[i];
        }
        else if(vec[i] == mx)
            opt.push_back(i);
    }
    return make_pair(opt[0], opt.back());
}
int stadium(int N, std::vector<std::vector<int>> F)
{
    vector<int> temp;
    int mask, i, j, cnt=0, n=N;
    srand(time(NULL));
    vector<vector<int> > orgf = F;
    for(i=0; i<N; i++){
        vector<int> f;
        for(j=0; j<N; j++){
            if(!F[i][j])
                f.push_back(j), cnt++;
        }
        if(!f.empty()){
            if(!consecutive(f))
                return 0;
            temp.push_back(i);
            l[i] = f[0];
            r[i] = f.back();
        }
        else{
            l[i] = r[i] = -1;
        }
    }
    if(!consecutive(temp))
        return 0;
    for(i=0; i<N; i++){
        for(j=0; j<N; j++){
            psumc[i+1][j+1] = psumc[i+1][j] + F[i][j];
            psumr[i+1][j+1] = psumr[i][j+1] + F[i][j];
        }
    }
    for(i=0; i<N; i++){
        for(j=i; j<N; j++){
            //printf("i=%d l=%d r=%d\n", i,l[i], r[i]);
            if(l[i]==-1 || l[j] == -1)
                continue;
            int temp = psumr[j+1][l[i]+1] - psumr[i][l[i]+1];
            if(l[i] <= r[j])
                temp += psumc[j+1][r[j]+1] - psumc[j+1][l[i]];
            else
                temp += psumc[j+1][l[i]+1] - psumc[j+1][r[j]];

            int temp2 = psumr[j+1][r[j]+1] - psumr[i][r[j]+1];
            if(l[i] <= r[j])
                temp2 += psumc[i+1][l[i]+1] - psumc[i+1][r[j]];
            else
                temp2 += psumc[i+1][r[j]+1] - psumc[i+1][l[i]];
            //printf("i=%d j=%d temp=%d temp2=%d\n", i, j, temp, temp2);
            if(temp && temp2)
                return 0;
        }
    }
    for(i=0; i<N; i++){
        for(j=i; j<N; j++){
            //printf("i=%d l=%d r=%d\n", i,l[i], r[i]);
            if(l[i]==-1 || l[j] == -1)
                continue;
            int temp = psumr[j+1][r[i]+1] - psumr[i][r[i]+1];
            if(r[i] <= l[j])
                temp += psumc[j+1][l[j]+1] - psumc[j+1][r[i]];
            else
                temp += psumc[j+1][r[i]+1] - psumc[j+1][l[j]];

            int temp2 = psumr[j+1][l[j]+1] - psumr[i][l[j]+1];
            if(r[i] <= l[j])
                temp2 += psumc[i+1][r[i]+1] - psumc[i+1][l[j]];
            else
                temp2 += psumc[i+1][l[j]+1] - psumc[i+1][r[i]];
            //printf("i=%d j=%d temp=%d temp2=%d\n", i, j, temp, temp2);
            if(temp && temp2)
                return 0;
        }
    }
    for(i=0; i<N; i++){
        for(j=i; j<N; j++){
            //printf("i=%d l=%d r=%d\n", i,l[i], r[i]);
            if(l[i]==-1 || l[j] == -1)
                continue;
            int temp = psumr[j+1][l[i]+1] - psumr[i][l[i]+1];
            if(l[i] <= l[j])
                temp += psumc[j+1][l[j]+1] - psumc[j+1][l[i]];
            else
                temp += psumc[j+1][l[i]+1] - psumc[j+1][l[j]];

            int temp2 = psumr[j+1][l[j]+1] - psumr[i][l[j]+1];
            if(l[i] <= l[j])
                temp2 += psumc[i+1][l[i]+1] - psumc[i+1][l[j]];
            else
                temp2 += psumc[i+1][l[j]+1] - psumc[i+1][l[i]];
            //printf("i=%d j=%d temp=%d temp2=%d\n", i, j, temp, temp2);
            if(temp && temp2)
                return 0;
        }
    }
    for(i=0; i<N; i++){
        for(j=i; j<N; j++){
            //printf("i=%d l=%d r=%d\n", i,l[i], r[i]);
            if(l[i]==-1 || l[j] == -1)
                continue;
            int temp = psumr[j+1][r[i]+1] - psumr[i][r[i]+1];
            if(r[i] <= r[j])
                temp += psumc[j+1][r[j]+1] - psumc[j+1][r[i]];
            else
                temp += psumc[j+1][r[i]+1] - psumc[j+1][r[j]];

            int temp2 = psumr[j+1][r[j]+1] - psumr[i][r[j]+1];
            if(r[i] <= r[j])
                temp2 += psumc[i+1][r[i]+1] - psumc[i+1][r[j]];
            else
                temp2 += psumc[i+1][r[j]+1] - psumc[i+1][r[i]];
            //printf("i=%d j=%d temp=%d temp2=%d\n", i, j, temp, temp2);
            if(temp && temp2)
                return 0;
        }
    }
    return cnt;
}
#endif
int biggest_stadium(int N, std::vector<std::vector<int>> F){
    int mask = 0, i, j, r=-1, c=-1;
    for(i=0; i<N; i++){
        for(j=0; j<N; j++){
            if(F[i][j]){
                r=i;
                c=j;
            }
        }
    }
    if(r==-1 && c==-1)
        return N*N;
    int b1 = r, b2 = N-1-r, a1 = c, a2 = N-1-c;
    int mx = 0;
    mx = max(mx, N*b1 + N*a1 - a1*b1);
    mx = max(mx, N*b2 + N*a1 - a1*b2);
    mx = max(mx, N*b2 + N*a2 - a2*b2);
    mx = max(mx, N*b1 + N*a2 - a2*b1);
    return mx;
}

Compilation message

soccer.cpp: In function 'int biggest_stadium(int, std::vector<std::vector<int> >)':
soccer.cpp:163:9: warning: unused variable 'mask' [-Wunused-variable]
  163 |     int mask = 0, i, j, r=-1, c=-1;
      |         ^~~~

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 0 ms 344 KB partial

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 1 ms 348 KB ok
8 Correct 14 ms 2396 KB ok
9 Correct 215 ms 31768 KB ok

Subtask #2
0.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Partially correct 0 ms 344 KB partial
4 Partially correct 0 ms 348 KB partial
5 Partially correct 1 ms 348 KB partial
6 Partially correct 0 ms 348 KB partial
7 Partially correct 0 ms 348 KB partial
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 348 KB ok
10 Incorrect 0 ms 348 KB wrong
11 Halted 0 ms 0 KB -

Subtask #3
0.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 0 ms 344 KB partial
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Partially correct 0 ms 344 KB partial
5 Partially correct 0 ms 348 KB partial
6 Partially correct 1 ms 348 KB partial
7 Partially correct 0 ms 348 KB partial
8 Partially correct 0 ms 348 KB partial
9 Correct 0 ms 348 KB ok
10 Correct 0 ms 348 KB ok
11 Incorrect 0 ms 348 KB wrong
12 Halted 0 ms 0 KB -

Subtask #4
0.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 0 ms 344 KB partial
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Partially correct 0 ms 344 KB partial
7 Partially correct 0 ms 348 KB partial
8 Partially correct 1 ms 348 KB partial
9 Partially correct 0 ms 348 KB partial
10 Partially correct 0 ms 348 KB partial
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Incorrect 0 ms 348 KB wrong
14 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 0 ms 344 KB partial
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Partially correct 0 ms 344 KB partial
7 Partially correct 0 ms 348 KB partial
8 Partially correct 1 ms 348 KB partial
9 Partially correct 0 ms 348 KB partial
10 Partially correct 0 ms 348 KB partial
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Incorrect 0 ms 348 KB wrong
14 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 0 ms 344 KB partial
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 1 ms 348 KB ok
9 Correct 14 ms 2396 KB ok
10 Correct 215 ms 31768 KB ok
11 Partially correct 0 ms 344 KB partial
12 Partially correct 0 ms 348 KB partial
13 Partially correct 1 ms 348 KB partial
14 Partially correct 0 ms 348 KB partial
15 Partially correct 0 ms 348 KB partial
16 Correct 0 ms 348 KB ok
17 Correct 0 ms 348 KB ok
18 Incorrect 0 ms 348 KB wrong
19 Halted 0 ms 0 KB -