oj.uz

Submission #824587

# Submission time Handle Problem Language Result Execution time Memory
824587 2023-08-14T08:02:27 Z 이동현(#10361) Robogolf (ROI19_golf) C++17
0 / 100
 5000 ms 524288 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define int long long
using namespace std;

const int mod = 998244353;

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int n, m, k;

	// n = 1000, m = 1000, k = 300000;
	// mt19937 gen(2353);
	// uniform_int_distribution<int> uid(-100, 100);
	// vector<array<int, 3>> a(k);
	// for(int i = 0; i < k; ++i){
	// 	a[i] = {i * (n * m / k) / m, i * (n * m / k) % m, uid(gen)};
	// }

	cin >> n >> m >> k;
	vector<array<int, 3>> a(k);
	for(int i = 0; i < k; ++i){
		cin >> a[i][0] >> a[i][1] >> a[i][2];
		--a[i][0], --a[i][1];
	}

	sort(a.begin(), a.end(), [&](array<int, 3>&x, array<int, 3>&y){
		return x[0] + x[1] < y[0] + y[1] || (x[0] + x[1] == y[0] + y[1] && x[1] < y[1]);
	});

	int ans = 0;
	auto sol = [&](int bt){
		vector<int> dp(n + m - 1 + bt + 10);

		int ap = k - 1;
		for(int i = n + m - 2 + bt; i >= 0; i -= 2){
			auto pos = [&](int x, int y){
				assert((n + bt - x - 1 - (m - y - 1)) % 2 == 0);
				return m - 1 + (n + bt - x - 1 - (m - y - 1)) / 2 + 4;
			};
			while(ap >= 0 && a[ap][0] + a[ap][1] == i){
				dp[pos(a[ap][0], a[ap][1])] = a[ap][2];
				--ap;
			}

			// cout << i << endl;
			// for(auto&j:dp) cout << j << ' ';
			// cout << endl;

			for(int x = 0; x <= i; ++x){
				int y = i - x;
				if(x < n && y < m){
					(ans += dp[pos(x, y)] + mod * 2) %= mod;
					// cout << dp[pos(x, y)] << endl;
				}
			}
				// cout << endl;

			for(int i = 1; i + 1 < (int)dp.size(); ++i){
				if(dp[i] < dp[i - 1] && dp[i] < dp[i + 1]){
					dp[i] = min(dp[i - 1], dp[i + 1]);
				}
			}
			while(ap >= 0 && a[ap][0] + a[ap][1] == i - 1){
				int j = ap;
				while(j - 1 >= 0 && a[j - 1][0] + a[j - 1][1] == i - 1 && a[j][1] - 1 == a[j - 1][1]){
					--j;
				}

				int p = pos(a[j][0] + 1, a[j][1]);
				assert(p > 0);
				dp[p] = min(a[j][2], max(dp[p], dp[p - 1]));
				for(int k = j; k < ap; ++k){
					dp[p + k - j + 1] = min(a[k][2], a[k + 1][2]);
				}
				assert(p + ap - j + 1 + 1 < (int)dp.size());
				dp[p + ap - j + 1] = min(a[ap][2], max(dp[p + ap - j + 1], dp[p + ap - j + 2]));

				ap = j - 1;			
			}
		}
	};
	sol(0);
	sol(1);

	cout << ans << '\n';
	
	return 0;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 240 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 308 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 9 ms 212 KB Output is correct
10 Incorrect 43 ms 2644 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5018 ms 3424 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 240 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 308 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 9 ms 212 KB Output is correct
10 Incorrect 43 ms 2644 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5048 ms 4196 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5048 ms 4196 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 240 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 308 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 9 ms 212 KB Output is correct
10 Incorrect 43 ms 2644 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 181 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 240 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 308 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 9 ms 212 KB Output is correct
10 Incorrect 43 ms 2644 KB Output isn't correct
11 Halted 0 ms 0 KB -