SCPC 2021 2차 대회 후기

망했다.

1, 2번은 쉽게 풀 수 있었고 3번은 풀이를 생각해서 잘 짰는데 실수를 많이 해서

끝나고 5분 뒤에 제대로 푼 것 같다. (맞았는지는 모르겠다.)

5번은 브루트포스하게 N=10인 경우 구해서 3점을 맞을 수 있었다.

4번은 KMP로 2번 테케까지 긁을 수 있다는걸 알고있었지만, 3번에 매달리고 있어서 풀어보지도 않았다.

 

3. 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1100;
ll M;
ll arr[N][N], sq[N][N], tr[N][N], ir[N][N];

ll chk(ll x,ll y){
	if(x>=0 && x<N && y>=0 && y<=N) return true;
	return false;
}

ll f1(ll x, ll y, ll w){
	if(w==0) return 0;
	ll res=0, tx, ty;
	res+=sq[x][y];
	res-=ir[x][y-w];
	res+=ir[x-w-1][y+1];
	res-=sq[x][y-w-1];
	return res;
}

ll f2(ll x, ll y, ll w){
	if(w==0) return 0;
	ll res=0;
	res+=tr[x+w-1][y];
	res-=tr[x-1][y-w];
	res-=sq[x-1][y];
	res+=sq[x-1][y-w];	
	return res;
}

ll f3(ll x, ll y, ll w){
	if(w==0) return 0;
	ll res=0;
	res+=sq[x][y+w-1];
	res-=tr[x-1][y+w-1];
	res+=tr[x-w-1][y-1];
	res-=sq[x][y-1];
	return res;
}

ll f4(ll x, ll y, ll w){
	if(w==0) return 0;
	ll res=0;
	res+=ir[x+w-1][y];
	res-=ir[x-1][y+w];
	res-=sq[x-1][y+w-1];
	res+=sq[x-1][y-1];
	return res;
}

int main(){
	ll T;
	scanf("%lld",&T);
	for(ll ca=1; ca<=T; ++ca){
		printf("Case #%lld\n",ca);
		ll n, k;
		scanf("%lld%lld",&n,&k);
		M=n+2*k;
		for(int i=0; i<N; ++i) for(int j=0; j<N; ++j) arr[i][j]=sq[i][j]=ir[i][j]=tr[i][j]=0;
		for(int i=2*k+2; i<n+2*k+2; ++i) for(int j=2*k+2; j<n+2*k+2; ++j) scanf("%lld",&arr[i][j]);
		for(int i=1; i<N; ++i){
			for(int j=1; j<N; ++j){
				sq[i][j]=arr[i][j]-sq[i-1][j-1]+sq[i-1][j]+sq[i][j-1];
				tr[i][j]=arr[i][j]+tr[i-1][j]+tr[i-1][j-1];
				if(i>1) tr[i][j]-=tr[i-2][j-1];
			}
			for(int j=N-2; j>=0; j--){
				ir[i][j]=arr[i][j]+ir[i-1][j]+ir[i-1][j+1];
				if(i>1) ir[i][j]-=ir[i-2][j+1];
			}
		}
		//for(int i=0; i<M; puts(""), ++i) for(int j=0; j<M; ++j) printf("%2lld %2lld %2lld | ",sq[i][j],tr[i][j],ir[i][j]);
		ll pr=0;
		for(int i=k+2; i<n+3*k+2; ++i){
			ll res=0;
			for(int j=k+2; j<n+3*k+2; ++j){
				res+=f3(i,j,k);
				res+=f4(i+1,j,k-1);
				res-=f1(i,j-1,k);
				res-=f2(i+1,j-1,k-1);
				//printf("%2lld %2lld %2lld %2lld %2lld | ",f3(i,j,k),f4(i+1,j,k-1),f1(i,j-1,k),f2(i+1,j-1,k-1),res);
				pr=max(pr,res);
			}
			//puts("");
		}
		printf("%lld\n",pr);
	}
}

 

실수도 많았고 맞을 수 있는걸 틀려서 상당히 답답했다.

한 1년 반쯤 놀면서 허송세월 보낸게 실감이 났다.

지금부터라도 다시 잡고 공부해보고자 한다.