oj.uz

Submission #824675

# Submission time Handle Problem Language Result Execution time Memory
824675 2023-08-14T08:43:25 Z 이동현(#10361) Robogolf (ROI19_golf) C++17
0 / 100
 5000 ms 5240 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;
	cin >> n >> m >> k;
    swap(n, m);
	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];
        swap(a[i][0], a[i][1]);
	}

    assert(m <= 5);

	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(m + 4), ndp(m + 4);

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

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

            if(cnt > 15 && i < n && n > 1000 && m <= 5){
                int nxt = 20 + i % 2;
                if(ap >= 0) nxt = max(nxt, a[ap][0] + a[ap][1] + 20 + (a[ap][0] + a[ap][1] + i) % 2);

                if(nxt < i){
                    int add = 0;
                    for(int x = 0; x <= i; ++x){
                        int y = i - x;
                        if(x < n && y < m){
                            (add += dp[y] + mod * 2) %= mod;
                        }
                    }

                    (ans += add * (i - nxt) / 2 % mod + mod) %= mod;
                    i = nxt;
                    cnt = 0;
                }
            }

			if(!bt){
				for(int x = 0; x <= i; ++x){
					int y = i - x;
					if(x < n && y < m){
						(ans += dp[y] + mod * 2) %= mod;
					}
				}
			}

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

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

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 Correct 1 ms 260 KB Output is correct
7 Runtime error 1 ms 468 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 25 ms 724 KB Output is correct
4 Correct 1901 ms 2644 KB Output is correct
5 Execution timed out 5020 ms 2772 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1885 ms 2644 KB Output is correct
2 Runtime error 21 ms 5240 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 Correct 1 ms 260 KB Output is correct
7 Runtime error 1 ms 468 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #5
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 5240 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 5240 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 Correct 1 ms 260 KB Output is correct
7 Runtime error 1 ms 468 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 Correct 1 ms 260 KB Output is correct
7 Runtime error 1 ms 468 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -