제출 #935958

#제출 시각아이디문제언어결과실행 시간메모리
935958noyancanturkNafta (COI15_nafta)C++17
100 / 100
208 ms68068 KiB
#ifndef Local #pragma GCC optimize("O3,unroll-loops") const int lim=(1<<11); #else const int lim=(1<<11); #endif #include "bits/stdc++.h" using namespace std; //#define int int64_t #define pb push_back int mod=1e9+7; //const int mod=(1ll<<61)-1; using pii=pair<int,int>; char s[lim][lim]; int n,m,gn=0; bool vis[lim*lim]; int parent[lim*lim]; int val[lim*lim/2],ll[lim*lim/2],rr[lim*lim/2]; inline void dfs(int node,int par){ vis[node]=1; int x=node>>11,y=node&(2047); parent[node]=parent[par]; val[gn]+=s[x][y]-'0'; ll[gn]=min(ll[gn],y); rr[gn]=max(rr[gn],y); for(int dd:{1,-1,lim,-lim}){ if(!vis[node+dd]){ dfs(node+dd,node); } } } #define P(i,j) (((i)<<11)|(j)) int g[lim][lim]; int dp[2][lim],curl; int ansss=INT_MIN; inline void dnc(int l,int r,int optl,int optr){ int mid=(l+r)>>1; int opt=min(optr,mid-1); dp[curl][mid]=g[mid][opt]+dp[!curl][opt]; for(int i=opt;optl<=i;i--){ if(dp[curl][mid]<g[mid][i]+dp[!curl][i]){ dp[curl][mid]=g[mid][i]+dp[!curl][i]; opt=i; } } ansss=max(ansss,dp[curl][mid]); if(l<=mid-1)dnc(l,mid-1,optl,opt); if(mid+1<=r)dnc(mid+1,r,opt,optr); } struct inpout{ static const int sz=1<<16; char inp[sz]; int curc=0,len=0; inline char gc(){ if(curc==len){ len=(int)fread(inp,1,sz,stdin); curc=0; if(!len)return -1; } return inp[curc++]; } inline void readstr(char*c,int ll){ for(int i=0;i<ll;i++){ c[i]=gc(); } gc(); } inline int readint(){ char c=gc(); bool isneg=(c=='-'); int ans=0; if(!isneg)ans=c-'0'; c=gc(); while('0'<=c&&c<='9'){ ans=10*ans+c-'0'; c=gc(); } if(isneg)return -ans; return ans; } }io; inline void solve(){ n=io.readint(),m=io.readint(); for(int i=0;i<m+2;i++){ s[0][i]=s[n+1][i]='.'; vis[P(0,i)]=vis[P(n+1,i)]=1; } for(int i=1;i<=n;i++){ vis[P(i,0)]=vis[P(i,m+1)]=1; for(int j=1;j<=m;j++){ if((s[i][j]=io.gc())=='.'){ vis[P(i,j)]=1; } } io.gc(); } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(!vis[P(i,j)]){ val[gn]=0; ll[gn]=INT_MAX; rr[gn]=-1; parent[P(i,j)]=gn; dfs(P(i,j),-1); gn++; } } } for(int i=0;i<gn;i++){ g[ll[i]][0]+=val[i]; g[ll[i]][ll[i]]-=val[i]; g[rr[i]+1][0]-=val[i]; g[rr[i]+1][ll[i]]+=val[i]; } for(int i=0;i<=m;i++){ for(int j=1;j<=m;j++){ g[i][j]+=g[i][j-1]; } } for(int i=0;i<=m;i++){ for(int j=1;j<=m;j++){ g[j][i]+=g[j-1][i]; } } dp[0][0]=0; for(int i=1;i<=m;i++){ dp[0][i]=g[i][0]; ansss=max(ansss,dp[0][i]); } cout<<ansss<<"\n"; for(int i=1;i<m;i++){ ansss=INT_MIN; curl=i&1; dnc(i,m,1,m); cout<<ansss<<"\n"; } } signed main(){ #ifdef Local freopen(".in","r",stdin); freopen(".out","w",stdout); #endif solve(); }

컴파일 시 표준 에러 (stderr) 메시지

nafta.cpp: In function 'void solve()':
nafta.cpp:29:28: warning: array subscript -1 is below array bounds of 'int [4194304]' [-Warray-bounds]
   29 |     parent[node]=parent[par];
      |                  ~~~~~~~~~~^
nafta.cpp:23:5: note: while referencing 'parent'
   23 | int parent[lim*lim];
      |     ^~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...