Submission #106393

#TimeUsernameProblemLanguageResultExecution timeMemory
106393antimirageTwo Dishes (JOI19_dishes)C++14
0 / 100
313 ms83568 KiB
/** 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]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...