Submission #513563

#TimeUsernameProblemLanguageResultExecution timeMemory
513563Killer2501Divide and conquer (IZhO14_divide)C++14
100 / 100
46 ms22340 KiB
#include <bits/stdc++.h> #define ll long long #define ld long double #define ull unsigned long long #define pb push_back #define pll pair<ll, ll> #define pii pair<int, int> #define fi first #define se second using namespace std; const int N = 3e5+5; const int M = (1<<17); const ll inf = 1e15; const ll mod = 1e15+7; int n, t, k, m, d[N], in[N], out[N]; ll ans, tong, a[N], b[N], c[N]; string s[N]; struct node { int x[2]; set<int> vi; node(){} node( int _x, int _y) { x[0] = _x; x[1] = _y; } }; vector<node> q; vector<int> adj[N], kq; void add(int x, int y) { for(int i = 0, j = 30; j >= 0; j --) { int t = (x >> j & 1); if(q[i].x[t] == 0) { q[i].x[t] = q.size(); q.pb(node(0, 0)); } i = q[i].x[t]; q[i].vi.insert(y); } } int get(int x, int l, int r) { int total = 0; for(int i = 0, j = 30; j >= 0; j --) { int t = (x >> j & 1); int nxt = q[i].x[t^1]; auto it = q[nxt].vi.lower_bound(l); if(it != q[nxt].vi.end() && (*it) <= r) { i = nxt; total += (1<<j); } else i = q[i].x[t]; } return total; } void dfs(int u) { in[u] = ++k; for(int v: adj[u])dfs(v); out[u] = k; } void sol() { cin >> n; a[0] = inf; for(int i = 1; i <= n; i ++) { cin >> d[i] >> b[i] >> c[i]; c[i] += c[i-1]; b[i] += b[i-1]; tong = c[i]-d[i]; int l = 1, r = i-1, mid; while(l <= r) { mid = (l+r)>>1; if(tong >= a[mid])r = mid-1; else l = mid+1; } ans = max(ans, b[i]-b[r]); a[i] = min(c[i-1]-d[i], a[i-1]); } cout << ans; } int main() { cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0); #define task "test" if(fopen(task".inp", "r")) { freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); } int ntest = 1; //cin >> ntest; while(ntest -- > 0) sol(); }

Compilation message (stderr)

divide.cpp: In function 'int main()':
divide.cpp:99:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |   freopen(task".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
divide.cpp:100:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |   freopen(task".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...