oj.uz

답안 #477555

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
477555 2021-10-02T15:33:15 Z cheissmart Two Dishes (JOI19_dishes) C++14
0 / 100
 10000 ms 51456 KB 
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

string _reset = "\u001b[0m", _yellow = "\u001b[33m", _bold = "\u001b[1m";
void DBG() { cerr << "]" << _reset << endl; }
template<class H, class...T> void DBG(H h, T ...t) {
	cerr << to_string(h);
	if(sizeof ...(t)) cerr << ", ";
	DBG(t...);
}
#ifdef CHEISSMART
#define debug(...) cerr << _yellow << _bold << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define debug(...)
#endif

const int INF = 1e9 + 7, N = 1e6 + 7;

int p[N], q[N];
ll a[N], b[N], s[N], t[N];
V<pi> G[N];

signed main()
{
	IO_OP;
	
	int n, m;
	cin >> n >> m;
	for(int i = 1; i <= n; i++) {
		cin >> a[i] >> s[i] >> p[i];
		a[i] += a[i - 1];
	}
	for(int i = 1; i <= m; i++) {
		cin >> b[i] >> t[i] >> q[i];
		b[i] += b[i - 1];
	}
	ll ans = 0;
	for(int i = 1; i <= n; i++) {
		/*
		a[i] + b[j] <= s[i]
		b[j] <= s[i] - a[i]
		*/
		int j = int(upper_bound(b, b + m + 1, s[i] - a[i]) - b);
		if(!j) continue;
		// if(i-th a before j-th b) ans += p[i]
		G[i].EB(j, p[i]);
	}
	for(int j = 1; j <= m; j++) {
		/*
		a[i] + b[j] <= t[j]
		a[i] <= t[j] - b[j]
		*/
		int i = int(upper_bound(a, a + n + 1, t[j] - b[j]) - a);
		if(!i) continue;
		// original: if(j-th b before i-th a) ans += q[j]
		ans += q[j];
		// now: if(i-th a before j-th b) ans += -q[j]
		G[i].EB(j, -q[j]);
	}
	map<int, ll> mp;
	for(int i = 1; i <= n; i++) {
		sort(ALL(G[i]), greater<pi>());
		for(auto [j, v] : G[i]) {
			// 0 ~ j - 1 add v
			for(int k = 0; k < j; k++)
				mp[k] += v;
			for(int k = 1; k <= m; k++)
				mp[k] = max(mp[k], mp[k - 1]);
			// ans += v;
			// mp[j] -= v;
			// if(mp[j] < 0) {
			// 	auto it = mp.find(j);
			// 	assert(it -> S < 0);
			// 	while(it -> S < 0) {
			// 		it++;
			// 		if(it != mp.end()) {
			// 			mp[it -> F] += mp[prev(it) -> F];
			// 			mp.erase(prev(it));
			// 		} else {
			// 			mp.erase(prev(it));
			// 			break;
			// 		}
			// 	}
			// }
		}
	}
	ans += mp[m];
	// for(auto [x, y]:mp) {
	// 	ans += y;
	// 	assert(y >= 0);
	// }
	cout << ans << '\n';

}

Compilation message

dishes.cpp: In function 'int main()':
dishes.cpp:76:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   76 |   for(auto [j, v] : G[i]) {
      |            ^

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 10004 ms 51456 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 23756 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 23756 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 23756 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 23756 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 23756 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 10004 ms 51456 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 10004 ms 51456 KB Time limit exceeded
2 Halted 0 ms 0 KB -