oj.uz

Submission #292995

# Submission time Handle Problem Language Result Execution time Memory
292995 2020-09-07T15:24:16 Z 임성재(#5807) Robogolf (ROI19_golf) C++17
0 / 100
 52 ms 4272 KB 
#include<bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define em emplace 
#define eb emplace_back
#define mp make_pair
#define all(v) (v).begin(), (v).end()

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int inf = 1e9;
const ll INF = 1e18;
const ll Mod = 998244353;

int n, m, k;
vector<pii> dp[1010], Dp[1010];
vector<int> chk[1010];

int main() {
	fast;

	cin >> n >> m >> k;

	for(int i=1; i<=k; i++) {
		int x, y, w;
		cin >> x >> y >> w;

		dp[x].eb(y, w);
		Dp[x].eb(y, w);
		chk[x].eb(y);
	}

	for(int i=1; i<=n; i++) Dp[i].eb(m+1, 0), dp[i].eb(m+1, 0), chk[i].eb(m+1);

	ll ans = 0;

	for(int i=n; i>=1; i--) {
		vector<int> v;
		sort(all(dp[i]));
		sort(all(Dp[i]));
		for(auto j : dp[i]) v.eb(j.fi), ans += Mod + j.se % Mod, ans %= Mod;
		for(auto j : Dp[i]) v.eb(j.fi);
		for(auto j : chk[i-1]) v.eb(j);

		if(i == 1) break;

		sort(all(v));

		int l[2] = {m+1, m+1}, val[2] = {0, 0};

		while(v.size()) {
			int j = v.back();
			v.pop_back();
			
			if(j == 0) break;
			if(j == m+1) continue;

			if(*lower_bound(all(chk[i-1]), j) == j) {
				l[0] = l[1] = j;
				val[0] = val[1] = lower_bound(all(dp[i-1]), mp(j, -inf-1)) -> se;
				v.eb(j-1);
				continue;
			}

			int x = 0, y = 0;
			int X = 0, Y = 0;
			if(lower_bound(all(Dp[i]), mp(j, -inf-1)) -> fi == j) x = lower_bound(all(Dp[i]), mp(j, -inf-1))->se;
			if(l[0] == j + 1) y = val[1];
			if(lower_bound(all(dp[i]), mp(j, -inf-1)) -> fi == j) X = lower_bound(all(dp[i]), mp(j, -inf-1))->se;
			if(l[1] == j + 1) Y = val[0];

			
			l[0] = j;
			val[0] = min(x, y);
			l[1] = j;
			val[1] = max(X, Y);


			if(val[0]) dp[i-1].eb(l[0], val[0]);
			if(val[1]) Dp[i-1].eb(l[1], val[1]);


			if((val[0] || val[1]) && v.size() && v.back() != j-1) v.eb(j-1);
		}
	}

	cout << ans;
}

Subtask #1
0 / 20.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 4272 KB Output is correct
2 Runtime error 1 ms 640 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

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

Subtask #5
0 / 6.0

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

Subtask #6
0 / 6.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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