# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
875964 | 2023-11-20T21:22:33 Z | auslander | Divide and conquer (IZhO14_divide) | C++17 | 0 ms | 2396 KB |
#include <iostream> #include <algorithm> #include <math.h> #include <sstream> #include <string> #include <iomanip> #include <queue> #include <stack> #include <deque> #include <set> #include <map> #include <vector> #include <iterator> using namespace std; //defines #define ll long long #define usg unsigned #define kap map #define print(x, n) for(int for_loop = 0; for_loop < n; for_loop++){cout<<x[for_loop]<<' ';}cout<<endl; #define read(x, n) for(int for_loop = 0; for_loop < n; for_loop++){cin>>x[for_loop];} #define speed ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); #define ratdig(x) cout << fixed << setprecision(x); #define xfixdig(x) cout << setprecision(x); #define multi int t; cin>>t; presolve(); while(t--) solve() #define single presolve(); solve(); return 0 #define rev(x) reverse(x.begin(), x.end()) #define all(x) x.begin(), x.end() //functions void yn(bool b) { if (b) { cout << "YES\n"; return; } cout << "NO\n"; } ll gcd(ll a, ll b) { if (a == 0) return b; if (b == 0) return a; return gcd(b % a, a); } ll lcm(ll a, ll b) { return (a * b) / gcd(a, b); } string to2(ll a) { string r = ""; for (ll i = a; i > 0; ) { ll k = i % 2; i /= 2; char c = k + 48; r += c; } if (a == 0) { r = "0"; } rev(r); return r; } ll binpow(ll a, ll b, ll mod = -1) { ll ans = 1; while (b) { if ((b & 1) == 1) { ans *= a; if (mod != -1) ans %= mod; } b >>= 1; a *= a; if (mod != -1) a %= mod; } return ans; } //body void presolve() { } const int N = 100005; ll gp[N], ep[N], g[N], e[N], x[N]; map < ll, ll > mp; void solve() { ll i, j, n, m, k; cin >> n; m = 0; k = 0; i = 0; ll res = 0; cin >> x[i] >> g[i] >> e[i]; m += g[i]; res = g[i]; gp[i] = m; ep[0] = e[0]; mp[ep[0]] = 1; for (i = 1; i < n; i++) { cin >> x[i] >> g[i] >> e[i]; res = max(g[i], res); m += g[i]; gp[i] = m; ep[i] = -x[i] + x[i - 1] + e[i]; ep[i] += ep[i - 1]; mp[ep[i]] = i + 1; } m = 0; ll q = 0; for (i = 0; i < n; i++) { //cout << ep[i] << ' '; //cout << gp[i] << ' '; //cout << m << ' ' << mp[m] << endl; if (mp[m] == 0) continue; if (mp[m] - 1 <= i) continue; ll w = gp[mp[m] - 1] - q; q = gp[i]; m = ep[i]; res = max(res, w); } //cout << endl; cout << res << endl; } int main() { speed; single; multi; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 2396 KB | Output is correct |
2 | Incorrect | 0 ms | 2396 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 2396 KB | Output is correct |
2 | Incorrect | 0 ms | 2396 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 2396 KB | Output is correct |
2 | Incorrect | 0 ms | 2396 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |