oj.uz

Submission #824604

# Submission time Handle Problem Language Result Execution time Memory
824604 2023-08-14T08:13:17 Z 이동현(#10361) Robogolf (ROI19_golf) C++17
0 / 100
 1588 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];});

	int ans = 0;
	auto sol = [&](int bt){
		vector<int> dp(n + m), ndp(n + m), pre(n + m);

		int ap = k - 1;
		for(int i = n + m - 2; i >= 0; --i){
            if(i + 2010 >= n + m - 2){
                for(int j = 0; j < n + m - 1; ++j){
                    if(!bt) ndp[j] = min(dp[j], dp[j + 1]);
                    else ndp[j] = max(dp[j], dp[j + 1]);
                }
                swap(dp, ndp);
                for(int j = 0; j < n + m; ++j){
                    pre[j] = dp[j];
                    if(j) pre[j] += pre[j - 1];
                }
            }

			while(ap >= 0 && a[ap][0] + a[ap][1] == i){
				dp[a[ap][1]] = a[ap][2];
				--ap;
			}

            if(i + 2010 >= n + m - 2){
                for(int j = 0; j < n + m; ++j){
                    pre[j] = dp[j];
                    if(j) pre[j] += pre[j - 1];
                }
            }

			if(!bt){
                int l = 0, r = 0;
                if(n <= m){
                    if(i <= n - 1) l = 0, r = i;
                    else if(i <= m - 1) l = i - (n - 1), r = m - 1;
                    else l = i - n + 1, r = m - 1;
                }
                else{
                    if(i <= m - 1) l = 0, r = i;
                    else if(i <= n - 1) l = 0, r = m - 1;
                    else l = i - n + 1, r = m - 1;
                }
                // cout << i << ' ' << l << ' ' << r << endl;
                // cout << pre[r] << endl;
				(ans += pre[r] % mod) %= mod;
                if(l) (ans += -pre[l - 1] % mod + mod) % mod;
			}

			bt ^= 1;
		}
	};
	sol(0);
	sol(1);

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

Compilation message

golf.cpp: In lambda function:
golf.cpp:78:56: warning: value computed is not used [-Wunused-value]
   78 |                 if(l) (ans += -pre[l - 1] % mod + mod) % mod;
      |                       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~

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 212 KB Output is correct
6 Incorrect 0 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

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

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 835 ms 5016 KB Output isn't correct
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 212 KB Output is correct
6 Incorrect 0 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1588 ms 7380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1588 ms 7380 KB Output isn't correct
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 212 KB Output is correct
6 Incorrect 0 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 174 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 212 KB Output is correct
6 Incorrect 0 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -