이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define int long long
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
int n,m , ma , mi , lol = 0;
char arr[2001][2001];
bool vis[2001][2001];
int dp[2001][2001];
int cost[2001][2001];
int level = 1;
void dc(int l,int r,int optl,int optr){
//cout<<"ggg"<<endl;
if(l>r)return ;
int mid = (l+r)/2;
pair<int,int> p = {-1e18,-1e18};
int sum = 0;
//cout<<level<<" "<<l<<" "<<r<<" "<<optl<<endl;
for(int i = min(optr,mid-1);i>=max(optl,0ll);i--){
sum=(cost[mid][m]-cost[mid][mid-1])-(cost[i][m]-cost[i][mid-1]);
p = max(p,make_pair(dp[level-1][i]+sum,i));
}
//cout<<"ff"<<endl;
dp[level][mid] = p.first;
int opt = p.second;
dc(l,mid-1,optl,opt);
dc(mid+1,r,opt,optr);
}
void dfs(int i,int j){
lol+=arr[i][j]-'0';
ma = max(ma,j);
mi = min(mi,j);
vis[i][j] = 1;
for(int e = 0;e<4;e++){
int nx = i+dx[e];
int ny = j+dy[e];
if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&arr[nx][ny]!='.'&&!vis[nx][ny]){
dfs(nx,ny);
}
}
}
signed main(){
ios_base::sync_with_stdio(false);cin.tie(0);
freopen("input.txt","r",stdin);
freopen("outout.txt","w",stdout);
cin>>n>>m;
for(int i = 1;i<=n;i++){
for(int j = 1;j<=m;j++){
cin>>arr[i][j];
}
}
for(int i = 1;i<=n;i++){
for(int j = 1;j<=m;j++){
if(!vis[i][j]&&arr[i][j]!='.'){
ma = 0 , mi = 1e9;
lol = 0;dfs(i,j);
cost[mi][ma]+=lol;
}
}
}
for(int i = 1;i<=m;i++){
for(int j = 1;j<=m;j++){
cost[i][j]+=cost[i][j-1];
}
}
for(int i = 1;i<=m;i++){
for(int j = 1;j<=m;j++){
cost[i][j]+=cost[i-1][j];
}
}
for(int i = 0;i<=m;i++){
for(int j = 0;j<=m;j++)dp[i][j] = -1e18;
}
dp[0][0] = 0;
level = 1;
while(level<=m){
//cout<<level<<endl;
dc(1,m,0,m-1);
int ma = 0;
for(int i = 1;i<=m;i++){
ma = max(ma,dp[level][i]);
}
cout<<ma<<"\n";
level++;
}
//cout<<"hhh"<<endl;
}
컴파일 시 표준 에러 (stderr) 메시지
nafta.cpp: In function 'int main()':
nafta.cpp:45:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
45 | freopen("input.txt","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
nafta.cpp:46:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
46 | freopen("outout.txt","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |