| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1103463 |
2024-10-21T03:30:33 Z |
doducanh |
Nafta (COI15_nafta) |
C++14 |
|
2 ms |
6736 KB |
///breaker
#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define fi first
#define se second
#define ii pair<int,int>
#define mp make_pair
#define in(x) freopen(x,"r",stdin)
#define out(x) freopen(x,"w",stdout)
#define bit(x,i) ((x>>i)&1)
#define lc (id<<1)
#define rc ((id<<1)^1)
const int maxn=2e3+7;
const int inf=1e9+7;
int dx[4]={1,0,0,-1};
int dy[4]={0,-1,1,0};
string s[maxn];
int val[maxn];
bool vst[maxn][maxn];
int w[maxn][maxn];
int I[maxn][maxn];
int dp[maxn][maxn];
int n,m;
bool check(int x,int y)
{
return (1<=x&&x<=n&&1<=y&&y<=m&&vst[x][y]==0&&s[x][y]>='0'&&s[x][y]<='9');
}
void dvc(int lvl,int l,int r,int rl,int rr)
{
if(l>r)return;
int m=(l+r)/2;
int best=-inf,pos;
for(int i=max(rl,m+1);i<=rr;i++){
int tmp=dp[lvl-1][i]+w[m][i];
if(tmp>best){
best=tmp;
pos=i;
}
}
dp[lvl][m]=best;
dvc(lvl,l,m-1,rl,pos);
dvc(lvl,m+1,r,pos,rr);
}
void sol(void){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>s[i];
s[i]=" "+s[i];
}
for(int i=1;i<=m;i++){
for(int j=0;j<=m;j++){
dp[i][j]=-inf;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(!check(i,j))continue;
queue<ii>q;
q.push({i,j});
int minn=j;
int maxx=j;
int tmp=0;
vst[i][j]=1;
while(q.size()){
int x=q.front().fi;
int y=q.front().se;
tmp+=(s[x][y]-'0');
minn=min(minn,y);
maxx=max(maxx,y);
q.pop();
for(int k=0;k<4;k++){
int nx=x+dx[k];
int ny=y+dy[k];
if(!check(nx,ny))continue;
q.push({nx,ny});
vst[nx][ny]=1;
}
}
for(int k=minn;k<=maxx;k++){
I[minn][k]+=tmp;
}
}
}
for(int i=m;i>=0;i--){
for(int j=1;j<=m;j++){
w[i][j]=w[i+1][j]+I[i+1][j];
}
}
dp[0][0]=0;
for(int i=1;i<=m;i++){
dvc(i,0,m,0,m);
int res=0;
for(int j=0;j<=m;j++){
res=max(res,dp[i][j]);
}
cout<<res<<"\n";
}
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t=1;
while(t--){
sol();
}
// you should actually read the stuff at the bottom
return 0;
}
/* stuff you should look for
* int overflow, array bounds
* special cases (n=1?)
* do smth instead of nothing and stay organized
* WRITE STUFF DOWN
* DON'T GET STUCK ON ONE APPROACH
*/
Compilation message
nafta.cpp: In function 'void dvc(long long int, long long int, long long int, long long int, long long int)':
nafta.cpp:44:8: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
44 | dvc(lvl,l,m-1,rl,pos);
| ~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6736 KB |
Output is correct |
| 2 |
Correct |
2 ms |
6736 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
6736 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6736 KB |
Output is correct |
| 2 |
Correct |
2 ms |
6736 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
6736 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6736 KB |
Output is correct |
| 2 |
Correct |
2 ms |
6736 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
6736 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
