oj.uz

Submission #328272

# Submission time Handle Problem Language Result Execution time Memory
328272 2020-11-16T04:09:44 Z arujbansal Orchard (NOI14_orchard) C++17
25 / 25
 141 ms 10092 KB 
#include <bits/stdc++.h>

#define FAST_IO ios_base::sync_with_stdio(false), cin.tie(nullptr)
#define FILE_IO freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
//#define int long long
using namespace std;


signed main() {
    FAST_IO;
    //FILE_IO;

    int n, m;
    cin >> n >> m;
    int grid[n + 1][m + 1];
    for (int i = 0; i <= n; i++) grid[i][0] = 0;
    for (int i = 0; i <= m; i++) grid[0][i] = 0;
    int ones = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> grid[i][j];
            if (grid[i][j]) ones++;
            else grid[i][j] = -1;
            grid[i][j] += grid[i - 1][j];
        }
    }
    int run = 0, maxi = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            run = 0;
            for (int k = 1; k <= m; k++) {
                run = max(run + grid[j][k] - grid[i - 1][k], grid[j][k] - grid[i - 1][k]);
                if (run < 0) run = 0;
                maxi = max(maxi, run);
            }
        }
    }
    cout << ones - maxi;
    return 0;
}

Subtask #1
4.0 / 4.0

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

Subtask #2
4.0 / 4.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 10092 KB Output is correct
2 Correct 74 ms 10092 KB Output is correct
3 Correct 75 ms 10092 KB Output is correct

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1920 KB Output is correct
2 Correct 15 ms 1900 KB Output is correct
3 Correct 15 ms 1900 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 5 ms 492 KB Output is correct
3 Correct 5 ms 492 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 4716 KB Output is correct
2 Correct 131 ms 4716 KB Output is correct
3 Correct 141 ms 4716 KB Output is correct