結果

問題 No.655 E869120 and Good Triangles
ユーザー ats5515ats5515
提出日時 2018-02-24 01:12:37
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 3,365 bytes
コンパイル時間 1,290 ms
コンパイル使用メモリ 107,516 KB
実行使用メモリ 13,640 KB
最終ジャッジ日時 2024-10-10 02:47:27
合計ジャッジ時間 8,220 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 TLE -
testcase_02 TLE -
testcase_03 TLE -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In member function 'long long int Sumvec::update(long long int, long long int)':
main.cpp:27:9: warning: no return statement in function returning non-void [-Wreturn-type]
   27 |         }
      |         ^
main.cpp: In member function 'long long int Sumvec::build()':
main.cpp:34:9: warning: no return statement in function returning non-void [-Wreturn-type]
   34 |         }
      |         ^

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <stdio.h>
using namespace std;
#define int long long
int MOD = 1000000007;
int INF = (int)1 << 60;
int dx[6] = { -1,-1,0,0,1,1 };
int dy[6] = { -1,0,-1,1,0,1 };
struct Sumvec {
	vector<int> v;
	vector<int> sum;

	void init(int N) {
		v.clear();
		v.resize(N + 1, 0);
	}
	int update(int i, int k) {
		v[i + 1] = k;
	}
	int build() {
		sum.clear();
		sum.resize(v.size(), 0);
		for (int i = 1; i < (int)sum.size(); i++) {
			sum[i] += sum[i - 1] + v[i];
		}
	}
	int get(int a, int b) {
		return sum[b] - sum[a];
	}
};
signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N, K, P;
	cin >> N >> K >> P;
	vector<vector<int> >A(N, vector<int>(N, INF));
	int x, y;

	queue<pair<int, int> > qu;
	for (int i = 0; i < K; i++) {
		cin >> x >> y;
		x--;
		y--;
		A[x][y] = 0;
		qu.push(make_pair(x, y));
	}
	while ((int)qu.size() > 0) {
		pair<int, int> p = qu.front(); qu.pop();
		pair<int, int> q;
		for (int i = 0; i < 6; i++) {
			q.first = p.first + dx[i];
			q.second = p.second + dy[i];

			if (q.first >= 0 && q.first < N && q.second >= 0 && q.second <= q.first) {
				if (A[q.first][q.second] > A[p.first][p.second] + 1) {
					A[q.first][q.second] = A[p.first][p.second] + 1;
					qu.push(q);
				}
			}
		}
	}
	cerr << "ok" << endl;
	for (int i = 0; i < N; i++) {
		for (int j = i + 1; j < N; j++) {
			A[i][j] = 0;
		}
	}
	//for (int i = 0; i < N; i++) {
	//	for (int j = 0; j <= i; j++) {
	//		cerr << A[i][j] << " ";
	//	}
	//	cerr << endl;
	//}
	vector<Sumvec> h(N);
	for (int i = 0; i < N; i++) {
		h[i].init(i + 1);
		for (int j = 0; j < i + 1; j++) {
			h[i].update(j, A[i][j]);
		}
		h[i].build();
	}
	vector<Sumvec> l(N);
	for (int i = 0; i < N; i++) {
		l[i].init(N);
		for (int j = 0; j < N; j++) {
			l[i].update(j, A[j][i]);
		}
		l[i].build();
	}
	vector<Sumvec> r(N);
	for (int i = 0; i < N; i++) {
		r[i].init(N - i);
		for (int j = 0; j < N - i; j++) {
			r[i].update(j, A[j + i][j]);
		}
		r[i].build();
	}
	cerr << "ok" << endl;
	int res = 0;
	int D[4000][4000];
	int sc[4000][4000];
	sc[0][0] = A[0][0];
	int d = 0;
	//cerr << sc[0][0] << endl;
	//cerr << h[1].get(0, 2) << endl;
	//cerr << h[1].sum[0] << endl;
	//cerr << h[1].sum[2] << endl;
	while (sc[0][0] < P && d < N - 1) {
		d++;
		sc[0][0] += h[d].get(0, d + 1);
		//cerr << sc[0][0] << endl;
	}
	if (sc[0][0] >= P) {
		res += N - d;
	}
	
	D[0][0] = d;
	for (int i = 1; i < N; i++) {
		cerr << i << endl;
		for (int j = 0; j <= i; j++) {
		
			int bb;
			if (j == 0) {
				bb = 0;
			}
			else if (j == i) {
				bb = -1;
			}
			else if (D[i - 1][j - 1] > D[i - 1][j]) {
				bb = -1;
			}
			else {
				bb = 0;
			}
			d = D[i - 1][j + bb];
			sc[i][j] = sc[i - 1][j + bb];
			if (sc[i][j] < P)continue;
			if (d == N) {
				d--;
			}
			//cerr << bb << endl;
			if (bb == -1) {
				sc[i][j] -= l[j - 1].get(i - 1, d + 1);
			}
			else {
				//cerr << i - j - 1 << " " << j << " " << d - (i - 1 - j) + 1 << endl;
				sc[i][j] -= r[i - 1 - j].get(j, d - (i - 1 - j) + 1);
				
			}
			//cerr << i << " " << j << endl;
			while (sc[i][j] < P && d < N - 1) {
				d++;
				sc[i][j] += h[d].get(j, j + d - i + 1);
			}
			if (sc[i][j] >= P) {
				res += N - d;
			}
			D[i][j] = d;
		}
	}
	cout << res << endl;
}
0