Submission #167770

#	Time	Username	Problem	Language	Result	Execution time	Memory
167770		Toirov_Sadi	Evacuation plan (IZhO18_plan)	C++17	0 / 100	15 ms	8568 KiB

plan

#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
• Subtask 2: 0 / 13
• Subtask 3: 0 / 12
• Subtask 4: 0 / 19
• Subtask 5: 0 / 46