# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
897989 |
2024-01-04T06:51:18 Z |
pan |
Orchard (NOI14_orchard) |
C++17 |
|
212 ms |
23900 KB |
#include <bits/stdc++.h>
//#include "bits_stdc++.h"
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
using namespace std;
typedef long long ll;
vector<vector<ll > > table;
int main()
{
ll n, m;
ll counter=0;
ll ans = LLONG_MAX;
bool gay;
cin >> n >> m;
table.assign(n+1, vector<ll> (m+1, 0));
for (ll i=1; i<=n; ++i)
{
for (ll j=1; j<=m; ++j)
{
cin >> gay;
if (gay) {counter++; table[i][j] = -1;}
else {table[i][j] = 1;}
table[i][j] += table[i-1][j] + table[i][j-1] - table[i-1][j-1];
}
}
for (ll i=1; i<=n; ++i)
{
ll best[n+1];
for (ll x=1; x<=n; ++x) best[x]=-LLONG_MAX;
for (ll j=1; j<=m; ++j)
{
ll maxx = 0;
for (ll k=1; k<=i; ++k)
{
if (j!=1) best[k]-=table[k-1][j-1] - table[k-1][j];
best[k] = max(best[k], table[k-1][j] + table[i][j-1]-table[k-1][j-1] );
maxx=max(best[k],maxx);
}
ans = min(ans, table[i][j]-maxx);
}
}
cout << counter + ans << endl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
440 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
604 KB |
Output is correct |
2 |
Correct |
2 ms |
604 KB |
Output is correct |
3 |
Correct |
2 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
125 ms |
23900 KB |
Output is correct |
2 |
Correct |
136 ms |
23900 KB |
Output is correct |
3 |
Correct |
125 ms |
23900 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
3416 KB |
Output is correct |
2 |
Correct |
25 ms |
3416 KB |
Output is correct |
3 |
Correct |
25 ms |
3420 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
444 KB |
Output is correct |
2 |
Correct |
6 ms |
604 KB |
Output is correct |
3 |
Correct |
6 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
206 ms |
7644 KB |
Output is correct |
2 |
Correct |
212 ms |
7848 KB |
Output is correct |
3 |
Correct |
201 ms |
7760 KB |
Output is correct |