Submission #106393

#	Time	Username	Problem	Language	Result	Execution time	Memory
106393		antimirage	Two Dishes (JOI19_dishes)	C++14	0 / 100	313 ms	83568 KiB

dishes

/**
	Elohim Esaim, Elohim Esaim I implore you...
**/
#include <bits/stdc++.h>
 
#define fr first
#define sc second
#define mk make_pair
#define pb push_back
#define all(s) s.begin(), s.end()
 
using namespace std;

const int N = 1e6 + 5;

int n, m;

long long pref[2][N], bal[2][N], t[2][N], s[2][N], ans, inf = 1e18;

vector < pair <int, long long> > vec[2][N];

main(){
	
	cin >> n >> m;
	
	for (int i = 1; i <= n; i++){
		
		scanf("%lld%lld%lld", &t[0][i], &s[0][i], &bal[0][i]);
		
		pref[0][i] = pref[0][i - 1] + t[0][i];
	}
	for (int i = 1; i <= m; i++){
		
		scanf("%lld%lld%lld", &t[1][i], &s[1][i], &bal[1][i]);
	
		pref[1][i] = pref[1][i - 1] + t[1][i];
	
		int pos = upper_bound( pref[0] + 1, pref[0] + n + 1, s[1][i] - pref[1][i] ) - pref[0] - 1;
		
		if (s[1][i] - pref[1][i] >= 0){
			
			if (vec[1][pos].empty() ) 
				vec[1][pos].pb( mk( i, bal[1][i] ) );
			else
				vec[1][pos].pb( mk( i, vec[1][pos].back().sc + bal[1][i] ) );
		}
	}
	for (int i = 1; i <= n; i++){
	
		int pos = upper_bound( pref[1] + 1, pref[1] + m + 1, s[0][i] - pref[0][i] ) - pref[1] - 1;
		
		if (s[0][i] - pref[0][i] >= 0){
			
			if (vec[0][pos].empty() ) 
				vec[0][pos].pb( mk( i, bal[0][i] ) );
			else
				vec[0][pos].pb( mk( i, vec[0][pos].back().sc + bal[0][i] ) );
		}
	}
	int i = 0, j = 0;
	
	while (i < n || j < m){
		
		if (i == n){
			if (pref[0][n] + pref[1][j + 1] <= s[1][j + 1])
				ans += bal[1][j + 1];
			j++;
			continue;
		}
		if (j == m){
			if (pref[1][m] + pref[0][i + 1] <= s[0][i + 1])
				ans += bal[0][i + 1];
			i++;
			continue;
		}
		long long val1 = 0, val2 = 0;
		
		int pos, t0 = 1, t1 = 1;
		
		if ( i <= m ){
			pos = upper_bound( all(vec[1][i]), mk(j, inf) ) - vec[1][i].begin() - 1;

			if (pos >= 0)
				val1 = -(vec[1][i].back().sc - vec[1][i][pos].sc);
			else if ( !vec[1][i].empty() )
				val1 = -vec[1][i].back().sc;
		}
		if ( j <= n ){
			pos = upper_bound( all(vec[0][j]), mk(i, inf) ) - vec[0][j].begin() - 1;
			
			if (pos >= 0)
				val2 = -(vec[0][j].back().sc - vec[0][j][pos].sc);
			else if ( !vec[0][j].empty() )
				val2 = -vec[0][j].back().sc;
		}
		if (pref[0][i + 1] + pref[1][j] > s[0][i + 1])
			t0 = 0;
		if (pref[1][j + 1] + pref[0][i] > s[1][j + 1])
			t1 = 0;
			
		//cout << i << " " << j << endl;
		//cout << t0 << endl;
		//cout << t1 << endl;
			
		if (val1 > val2){
			ans += bal[0][i + 1] * t0;
			i++;
		}
		else{
			ans += bal[1][j + 1] * t1;
			j++;
		}
	}
	cout << ans << endl;
}
/**
4 3
2 1 1
3 8 1
2 13 1
1 13 1
3 6 1
2 11 1
2 15 1
**/

Compilation message (stderr)

dishes.cpp:22:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
dishes.cpp: In function 'int main()':
dishes.cpp:28:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld", &t[0][i], &s[0][i], &bal[0][i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:34:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld", &t[1][i], &s[1][i], &bal[1][i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 3
• Subtask 3: 0 / 7
• Subtask 4: 0 / 39
• Subtask 5: 0 / 11
• Subtask 6: 0 / 9
• Subtask 7: 0 / 17
• Subtask 8: 0 / 9