앳코더90 - 004 - Cross Sum（★2）

https://atcoder.jp/contests/typical90/tasks/typical90_d

004 - Cross Sum（★2）

 

세로 가로가 H, W 인 2차원 배열을 입력받고

 

각 값을 가로 전체, 세로 전체 더한값이 해당 위치의 새로운 값이된다.

해당값을 계산해서 새로운 배열에 넣으면 된다는 생각만 가지고 그냥 구현을 갈겼더니 TLE가 나왔다.

별 2개만 보고 그저 그런문제 인지 알았다.

 

입력 제한을보니 H, W가 2000이다.

N^4풀이로는 턱없이 부족하다. prefix를 이용하여 미리 값을 다 더해놓고 바로바로 넣어주니 정답이다.

 

 

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define range(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef vector<int> vi;

const int INF = 100000000;
const double pi = 3.14159265358979;
const ll MOD = 1000000007;

int H, W;
int arr[2002][2002];
int prefixR[2002];
int prefixC[2002];
int ans[2002][2002];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> H >> W;

	rep1(i, H)
	{
		rep1(j, W)
		{
			cin >> arr[i][j];
		}
	}

	rep1(i, H)
	{
		int tot = 0;
		rep1(j, W)
		{
			tot += arr[i][j];
		}
		prefixR[i] = tot;
	}

	rep1(j, W)
	{
		int tot = 0;
		rep1(i, H)
		{
			tot += arr[i][j];
		}
		prefixC[j] = tot;
	}
	rep1(i, H)
	{
		rep1(j, W)
		{
			ans[i][j] = prefixR[i] + prefixC[j] - arr[i][j];
		}
	}

	rep1(i, H)
	{
		rep1(j, W)
		{
			cout<< ans[i][j] << " ";
		}
		cout << "\n";
	}
   
	return 0;
}