oj.uz

답안 #167770

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
167770 2019-12-10T05:56:30 Z Toirov_Sadi Evacuation plan (IZhO18_plan) C++17
0 / 100
 15 ms 8568 KB 
#include <bits/stdc++.h>

#define fr first
#define se second

using namespace std;

const long long N = 1e3 + 7;
const long long inf = 1e9 + 7;
const long long mod = 1e9 + 7;

int n;
int k;
int q[N];
int w[N];
int e[N];
int r[N];
int a[N][N];
int res = inf;
int go(int i, int j, int x, int y){
    if(i > n || j > n || i <= 0 || j <= 0){
        return 0;
    }
    int cnt = 0;
    for(int k = i; k < i + x; k ++){
        for(int h = j; h < j + x; h ++){
            cnt += (a[k][h] == y);
        }
    }return cnt;
}
void can(int x){
    int cnt = 0;
    int ans = 0, ans2 = 0;
    for(int i = 1; i <= n; i += x){
        for(int j = (cnt % 2 ? 0 : x) + 1; j <= n; j += 2 * x){
            ans += go(i, j, x, 0);
            ans += go(i, j + x * (cnt % 2 ? 1 : -1), x, 1);
            if(cnt % 2 == 0 && (j + 2 * x - 1) == n){
                ans += go(i, j + x, x, 1);
            }
        }
        for(int j = (cnt % 2 ? x : 0) + 1; j <= n; j += 2 * x){
            ans2 += go(i, j, x, 0);
            ans2 += go(i, j + x * (cnt % 2 ? -1 : 1), x, 1);
            if(cnt % 2 && (j + 2 * x - 1) == n){
                ans2 += go(i, j + x, x, 1);
            }
        }cnt ++;
    }res = min({res, ans, ans2});
}
int main()
{
    /// freopen("input.txt", "r", stdin);
    /// freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio( false );

    cin >> n >> k;
    for(int i = 1; i <= k; i ++){
        cin >> q[i] >> w[i] >> e[i] >> r[i];
        for(int j = q[i]; j <= e[i]; j ++){
            for(int k = w[i]; k <= r[i]; k ++){
                a[j][k] = 1;
            }
        }
    }
    can(1);
    cout << res << "\n";
    return 0;
    for(int i = 1; i * i <= n; i ++){
        if(n % i == 0){
            can(i);
            if(n / i != i && (n / i) < n){
                can(n / i);
            }
        }
    }cout << res << "\n";
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 2808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 2808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 2040 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 15 ms 8568 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 2808 KB Output isn't correct
2 Halted 0 ms 0 KB -