oj.uz

Submission #205693

# Submission time Handle Problem Language Result Execution time Memory
205693 2020-02-29T13:40:29 Z ZwariowanyMarcin Orchard (NOI14_orchard) C++14
25 / 25
 451 ms 23928 KB 
#include <bits/stdc++.h>
#define LL long long
#define LD long double
#define pb push_back
#define mp make_pair
#define ss(x) (int) x.size()
#define fi first
#define se second
#define cat(x) cerr << #x << " = " << x << endl
#define rep2(i, j, n) for (LL i = j; i <= n; ++i)
#define rep(i, j, n) for (int i = j; i <= n; ++i)
#define per(i, j, n) for (int i = n; j <= i; --i)
#define boost cin.tie(0);ios_base::sync_with_stdio(0);
#define vi vector <int>

using namespace std;

const int nax = 1e6 + 111;

int n, m;
LL f[nax];
LL best = 1e18;
int ones;
vector <vector <int>> a, g;

int main() {	
	scanf ("%d%d", &n, &m);
	
	a.resize(n + 5);
	g.resize(n + 5);
	
	rep(i, 0, n) a[i].resize(m + 5, 0);
	rep(i, 0, n) g[i].resize(m + 5, 0);
	
	rep(i, 1, n) rep(j, 1, m) {
		scanf ("%d", &a[i][j]);
		g[i][j] = (a[i][j] == 1) + g[i - 1][j];
		ones += (a[i][j] == 1);
	}
	
	rep(i, 1, n)
		rep(j, i, n) {
			rep(x, 1, m) f[x] = g[j][x] - g[i - 1][x];
			LL opt = 1e18;
			int h = j - i + 1;
			rep(x, 1, m) f[x] += f[x - 1];
			
			rep(x, 1, m) {
				opt = min(opt, 2 * f[x - 1] - h * (x - 1));
				best = min(best, ones + (h * x) - 2 * f[x] + opt);
			}
			
		}
	printf ("%lld\n", best);
			
	
	return 0;
}

Compilation message

orchard.cpp: In function 'int main()':
orchard.cpp:27:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d%d", &n, &m);
  ~~~~~~^~~~~~~~~~~~~~~~
orchard.cpp:36:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d", &a[i][j]);
   ~~~~~~^~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

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

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 632 KB Output is correct
2 Correct 6 ms 632 KB Output is correct
3 Correct 7 ms 636 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 23928 KB Output is correct
2 Correct 133 ms 23928 KB Output is correct
3 Correct 134 ms 23800 KB Output is correct

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 3448 KB Output is correct
2 Correct 31 ms 3500 KB Output is correct
3 Correct 29 ms 3480 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 376 KB Output is correct
2 Correct 18 ms 504 KB Output is correct
3 Correct 19 ms 508 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 446 ms 6432 KB Output is correct
2 Correct 451 ms 6328 KB Output is correct
3 Correct 448 ms 6264 KB Output is correct