oj.uz

Submission #1113215

# Submission time Handle Problem Language Result Execution time Memory
1113215 2024-11-16T03:57:12 Z votranngocvy Orchard (NOI14_orchard) C++14
20 / 25
 1000 ms 55176 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 5e3 + 2;
vector<vector<int>>a,pre;
vector<int>sum,suf;
int n,m,total;

bool check(int mid) {
    for (int l = 1; l <= n; l++)
        for (int r = l; r <= n; r++) {
            sum[0] = 0;
            for (int i = 1; i <= m; i++)
                sum[i] = sum[i - 1] + pre[r][i] - pre[l - 1][i];
            suf[m + 1] = 1e18;
            for (int i = m; i > 0; i--)
                suf[i] = min(suf[i + 1],2 * sum[i] - (r - l + 1) * i);
            for (int i = 1; i <= m; i++)
                if (suf[i + 1] <= mid + 2 * sum[i - 1] - total - (r - l + 1) * (i - 1)) return 1;
        }
    return 0;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    total = 0;
    a.assign(n + 5,vector<int>(m + 5));
    pre.assign(n + 5,vector<int>(m + 5,0));
    sum.assign(m + 5,0);
    suf.assign(m + 5,0);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            char x;
            cin >> x;
            a[i][j] = x - '0';
            total += a[i][j];
            pre[i][j] = pre[i - 1][j] + 1 - a[i][j];
        }
    int l = 0,r = n * m,ans = -1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (check(mid)) ans = mid,r = mid - 1;
        else l = mid + 1;
    }
    cout << ans << "\n";
}

Compilation message

orchard.cpp: In function 'bool check(int)':
orchard.cpp:15:26: warning: overflow in conversion from 'double' to '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} changes value from '1.0e+18' to '2147483647' [-Woverflow]
   15 |             suf[m + 1] = 1e18;
      |                          ^~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1104 KB Output is correct
2 Correct 2 ms 1272 KB Output is correct
3 Correct 2 ms 1104 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 55044 KB Output is correct
2 Correct 88 ms 55036 KB Output is correct
3 Correct 87 ms 55176 KB Output is correct

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 6600 KB Output is correct
2 Correct 17 ms 6600 KB Output is correct
3 Correct 16 ms 6600 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 560 KB Output is correct
2 Correct 40 ms 592 KB Output is correct
3 Correct 39 ms 592 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1053 ms 6480 KB Time limit exceeded
2 Halted 0 ms 0 KB -