oj.uz

Submission #261275

# Submission time Handle Problem Language Result Execution time Memory
261275 2020-08-11T15:45:06 Z Saboon Treatment Project (JOI20_treatment) C++14
4 / 100
 115 ms 7244 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 2e5 + 10;

ll T[maxn], L[maxn], R[maxn], C[maxn], p[maxn], dp[maxn];

int main(){
	ios_base::sync_with_stdio(false);
	ll n, m;
	cin >> n >> m;
	for (ll i = 1; i <= m; i++)
		cin >> T[i] >> L[i] >> R[i] >> C[i];
	if (*max_element(T+1, T+m+1) == 1){
		for (ll i = 1; i <= m; i++)
			p[i] = i;
		sort(p+1, p+m+1, [](ll a, ll b){ return R[a] < R[b]; });
		vector<ll> S;
		for (ll iit = 1; iit <= m; iit++){
			ll i = p[iit];
			if (L[i] == 1)
				dp[i] = C[i];
			else
				dp[i] = -1;
			if (S.empty()){
				if (dp[i] != -1)
					S.push_back(i);
				continue;
			}
			ll lo = -1, hi = S.size();
			while (hi - lo > 1){
				ll mid = (lo + hi) >> 1;
				if (R[S[mid]]+1 < L[i])
					lo = mid;
				else
					hi = mid;
			}
			if (hi == S.size())
				continue;
			if (dp[i] == -1 or dp[i] > dp[S[hi]] + C[i])
				dp[i] = dp[S[hi]] + C[i];
			while (!S.empty() and dp[S.back()] >= dp[i])
				S.pop_back();
			S.push_back(i);
		}
		ll answer = -1;
		for (ll i = 1; i <= m; i++)
			if (R[i] == n and dp[i] != -1 and (answer == -1 or answer > dp[i]))
				answer = dp[i];
		cout << answer << endl;
		return 0;
	}
	for (ll i = 1; i <= m; i++)
		p[i] = i;
	for (ll _ = 0; _ < m; _++){
		for (ll iit = 1; iit <= m; iit++){
			ll i = p[iit];
			if (L[i] == 1)
				dp[i] = C[i];
			for (ll jit = 1; jit <= m; jit++){
				ll j = p[jit];
				if (L[j] <= R[i] and abs(T[i]-T[j]) <= R[j]-L[i]+1 and dp[j] != -1)
					if (dp[i] == -1 or dp[i] > dp[j] + C[i])
						dp[i] = dp[j] + C[i];
			}
			for (ll jit = 1; jit <= m; jit++){
				ll j = p[jit];
				if (L[i] <= R[j] and abs(T[i]-T[j]) <= R[i]-L[j]+1 and dp[i] != -1){
					if (dp[j] == -1 or dp[j] > dp[i] + C[j])
						dp[j] = dp[i] + C[j];
				}
			}
		}
	}
	ll answer = -1;
	for (ll i = 1; i <= m; i++)
		if (R[i] == n and dp[i] != -1 and (answer == -1 or answer > dp[i]))
			answer = dp[i];
	cout << answer << endl;
}

Compilation message

treatment.cpp: In function 'int main()':
treatment.cpp:38:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (hi == S.size())
        ~~~^~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 7244 KB Output is correct
2 Correct 91 ms 6776 KB Output is correct
3 Correct 104 ms 6776 KB Output is correct
4 Correct 84 ms 6696 KB Output is correct
5 Correct 73 ms 6112 KB Output is correct
6 Correct 80 ms 6136 KB Output is correct
7 Correct 89 ms 6360 KB Output is correct
8 Correct 70 ms 6136 KB Output is correct
9 Correct 67 ms 6136 KB Output is correct
10 Correct 77 ms 6156 KB Output is correct
11 Correct 75 ms 6088 KB Output is correct
12 Correct 77 ms 6136 KB Output is correct
13 Correct 93 ms 6100 KB Output is correct
14 Correct 86 ms 6084 KB Output is correct
15 Correct 89 ms 6136 KB Output is correct
16 Correct 101 ms 6136 KB Output is correct
17 Correct 100 ms 6180 KB Output is correct
18 Correct 87 ms 6140 KB Output is correct

Subtask #2
0 / 5.0

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

Subtask #3
0 / 30.0

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

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 7244 KB Output is correct
2 Correct 91 ms 6776 KB Output is correct
3 Correct 104 ms 6776 KB Output is correct
4 Correct 84 ms 6696 KB Output is correct
5 Correct 73 ms 6112 KB Output is correct
6 Correct 80 ms 6136 KB Output is correct
7 Correct 89 ms 6360 KB Output is correct
8 Correct 70 ms 6136 KB Output is correct
9 Correct 67 ms 6136 KB Output is correct
10 Correct 77 ms 6156 KB Output is correct
11 Correct 75 ms 6088 KB Output is correct
12 Correct 77 ms 6136 KB Output is correct
13 Correct 93 ms 6100 KB Output is correct
14 Correct 86 ms 6084 KB Output is correct
15 Correct 89 ms 6136 KB Output is correct
16 Correct 101 ms 6136 KB Output is correct
17 Correct 100 ms 6180 KB Output is correct
18 Correct 87 ms 6140 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Incorrect 1 ms 384 KB Output isn't correct
21 Halted 0 ms 0 KB -