#include <bits/stdc++.h>
using namespace std;
//Optimizations
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//save time
#define endl '\n'
#define db(x) cerr << "> " << #x << ": " << x << endl
typedef long long ll;
//for sorting
#define all(a) a.begin(),a.end()
//Constants
#define PI 3.141592653593
#define MOD 1000000007LL
#define EPS 0.000000001
#define INF 0X3f3f3f3f
//loops
#define REP(i,n) for(int i=0;i<(n);++i)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define DFOR(i,a,b) for(int i=(a);i>=(b);--i)
//vectors
#define vi vector<int>
#define vll vector<ll>
#define vii vector<pair<int,int>>
#define vlll vector<pair<ll,ll>>
#define pb push_back
#define vb vector<bool>
//pairs
#define pi pair<int,int>
#define pll pair<ll,ll>
#define mp make_pair
#define f first
#define s second
//fast I/O
#ifndef _WIN32
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif
#define gc getchar
#define pc putchar
//If using cin and cout
#define IOS ios::sync_with_stdio(false)
#define TIE cin.tie(NULL);cout.tie(NULL)
//queue
#define di deque<int>
#define dll deque<ll>
#define qi queue<int>
#define PQ priority_queue
//general
#define E empty()
const int MAXN=2010;
void usaco(string filename) {
// #pragma message("be careful, freopen may be wrong")
freopen((filename + ".in").c_str(), "r", stdin);
freopen((filename + ".out").c_str(), "w", stdout);
}
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) {
cout << "["; for(int i = 0; i < v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";
}
template<typename A, typename B> istream& operator>>(istream& cin, pair<A, B> &p) {
cin >> p.first;
return cin >> p.second;
}
char g[MAXN][MAXN];
bool vis[MAXN][MAXN]= {false};
struct item{
int l = INT_MAX;
int r, value;
item(){
l = INT_MAX;
r = INT_MIN;
value = 0;
}
bool operator < (item & other){
return l < other.l;
}
};
struct event{
bool start;
int val, pos, id;
bool operator < (event & other){
return pos < other.pos;
}
};
int ids[MAXN][MAXN];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
int cost[MAXN][MAXN];
int n, m;
// int res[2005];
int C[2005][2005];
int before_dp[2005];
int current_dp[2005];
bool valid(int i, int j){
return i>=0 && j >= 0 && i < n && j < m;
}
// dp undirected graph.
void flood(int i, int j){
vis[i][j]=1;
REP(pos, 4){
int ci = dx[pos]+i;
int cj = dy[pos]+j;
if(valid(ci, cj) && !vis[ci][cj] && g[ci][cj] != '.'){
ids[ci][cj]=ids[i][j];
flood(ci, cj);
}
}
}
int gres = 0;
void solve(int l, int r, int optl, int optr){
if(l > r)
return;
int mid = (l+r)/2;
pi best = {-1, -1};
for(int k = optl ; k <= min(mid, optr); ++k){
best = max(best, {before_dp[k]+C[k][mid], k});
}
current_dp[mid]=best.f;
gres=max(gres, best.f);
solve(l, mid-1, optl, best.s);
solve(mid+1, r, best.s, optr);
}
int main(){
cin >> n >> m;
REP(i, n){
REP(j, m){
cin >> g[i][j];
}
}
int t_id = 1;
REP(i, n){
REP(j, m){
if(g[i][j]!= '.' && !vis[i][j]){
ids[i][j] = t_id;
vis[i][j]=1;
++t_id;
flood(i,j);
}
}
}
// REP(i, n){
// REP(j, m){
// cout << ids[i][j] << " ";
// }
// cout << endl;
// }
--t_id;
item ar[t_id];
vector<event> events;
REP(i, n){
REP(j, m){
if(ids[i][j])
{
ar[ids[i][j]-1].l = min(ar[ids[i][j]-1].l, j);
ar[ids[i][j]-1].r = max(ar[ids[i][j]-1].r, j);
ar[ids[i][j]-1].value+=g[i][j]-'0';
}
}
}
REP(i, t_id){
events.pb({1, ar[i].value, ar[i].l, i});
events.pb({0, ar[i].value, ar[i].r+1, i});
}
// sort(ar, ar+t_id);
// cout << endl << endl;
sort(all(events));
for(int i = 0; i < m; ++i){
int cur = 0;
bool used[t_id];
memset(used, 0, sizeof(used));
while(cur < (int)events.size() && events[cur].pos < i ){
used[events[cur].id]=1;
++cur;
}
int res = 0;
for(int j = 0; j <= m; ++j){
while(cur < (int)events.size() && events[cur].pos < j){
if(events[cur].start && !used[events[cur].id]){
res+=events[cur].val;
}else if(!used[events[cur].id]) res-=events[cur].val;
++cur;
}
C[i][j]=res;
// cout << C[i][j] << " ";
}
// cout << endl;
}
memset(current_dp, 0, sizeof(current_dp));
memset(before_dp, 0, sizeof(before_dp));
for(int i = 0; i <m ; ++i){
solve(0, m, 0, m);
swap(current_dp, before_dp);
cout << gres << endl;
}
}
Compilation message
nafta.cpp: In function 'void usaco(std::string)':
nafta.cpp:66:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
66 | freopen((filename + ".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
nafta.cpp:67:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
67 | freopen((filename + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
1004 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1004 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1004 KB |
Output is correct |
| 4 |
Correct |
1 ms |
876 KB |
Output is correct |
| 5 |
Correct |
1 ms |
876 KB |
Output is correct |
| 6 |
Correct |
1 ms |
876 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
1004 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1004 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1004 KB |
Output is correct |
| 4 |
Correct |
1 ms |
876 KB |
Output is correct |
| 5 |
Correct |
1 ms |
876 KB |
Output is correct |
| 6 |
Correct |
1 ms |
876 KB |
Output is correct |
| 7 |
Correct |
41 ms |
5404 KB |
Output is correct |
| 8 |
Correct |
27 ms |
5096 KB |
Output is correct |
| 9 |
Correct |
16 ms |
5996 KB |
Output is correct |
| 10 |
Correct |
32 ms |
4456 KB |
Output is correct |
| 11 |
Correct |
16 ms |
4204 KB |
Output is correct |
| 12 |
Correct |
12 ms |
4076 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
1004 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1004 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1004 KB |
Output is correct |
| 4 |
Correct |
1 ms |
876 KB |
Output is correct |
| 5 |
Correct |
1 ms |
876 KB |
Output is correct |
| 6 |
Correct |
1 ms |
876 KB |
Output is correct |
| 7 |
Correct |
41 ms |
5404 KB |
Output is correct |
| 8 |
Correct |
27 ms |
5096 KB |
Output is correct |
| 9 |
Correct |
16 ms |
5996 KB |
Output is correct |
| 10 |
Correct |
32 ms |
4456 KB |
Output is correct |
| 11 |
Correct |
16 ms |
4204 KB |
Output is correct |
| 12 |
Correct |
12 ms |
4076 KB |
Output is correct |
| 13 |
Execution timed out |
1095 ms |
51508 KB |
Time limit exceeded |
| 14 |
Halted |
0 ms |
0 KB |
- |
