oj.uz

Submission #77037

# Submission time Handle Problem Language Result Execution time Memory
77037 2018-09-20T08:13:50 Z win11905 Orchard (NOI14_orchard) C++11
25 / 25
 276 ms 14376 KB 
#include <bits/stdc++.h>
using namespace std;

int n, m, ans = 1e9;

int main() {
    scanf("%d %d", &n, &m);
    vector<vector<int>> dp(n+1, vector<int>(m+1));
    for(int i = 1; i <= n; ++i) for(int j = 1, ret; j <= m; ++j) scanf("%1d", &ret), dp[i][j] = ret + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1];
    for(int i = 0 ; i < n; ++i) for(int j = i+1; j <= n; ++j) {
        int mn = 1e9;
        for(int k = 1; k <= m; ++k) {
            mn = min(mn, 2 * (dp[j][k-1] - dp[i][k-1]) + (i - j) * (k-1));
            ans = min(ans, dp[n][m] - 2 * (dp[j][k] - dp[i][k]) + (j - i) * k + mn);
        }
    }
    printf("%d\n", ans);
}

Compilation message

orchard.cpp: In function 'int main()':
orchard.cpp:7:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
orchard.cpp:9:84: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i <= n; ++i) for(int j = 1, ret; j <= m; ++j) scanf("%1d", &ret), dp[i][j] = ret + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1];

Subtask #1
4.0 / 4.0

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

Subtask #2
4.0 / 4.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 12388 KB Output is correct
2 Correct 108 ms 12388 KB Output is correct
3 Correct 107 ms 14376 KB Output is correct

Subtask #4
3.0 / 3.0

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

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 14376 KB Output is correct
2 Correct 8 ms 14376 KB Output is correct
3 Correct 9 ms 14376 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 14376 KB Output is correct
2 Correct 215 ms 14376 KB Output is correct
3 Correct 276 ms 14376 KB Output is correct