Submission #1209553

#TimeUsernameProblemLanguageResultExecution timeMemory
1209553tkm_algorithmsCatfish Farm (IOI22_fish)C++20
0 / 100
43 ms7232 KiB
/** * In the name of Allah * We are nothing and you're everything **/ #include <bits/stdc++.h> #include "fish.h" using namespace std; using ll = long long; using ull = uint64_t; #define all(x) begin(x), end(x) #define sz(x) (int)(x).size() //#define int long long const char nl = '\n'; //const int N = 2e5+1; const ll inf = 0x3f3f3f3f3f3f3f3fll; const int mod = 1e9+7; struct segtree{ vector<ll> tree; int size; void init(int n) { size = 1; while (size < n)size <<= 1; tree.assign(2*size-1, 0ll); } void set(int i, ll v, int x, int lx, int rx) { if (rx-lx==1) { tree[x] = v; return; } int mid = lx+rx>>1; if (i < mid)set(i, v, 2*x+1, lx, mid); else set(i, v, 2*x+2, mid, rx); tree[x] = max(tree[2*x+1], tree[2*x+2]); } void set(int i, ll v) { set(i, v, 0, 0, size); } ll get(int l, int r, int x, int lx, int rx) { if (rx <= l || r <= lx)return 0ll; if (lx >= l && rx <= r)return tree[x]; int mid = lx+rx>>1; return max(get(l, r, 2*x+1, lx, mid), get(l, r, 2*x+2, mid, rx)); } ll get(int l, int r) { return get(l, r, 0, 0, size); } }; long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) { vector<int> a(N+1); for (int i = 0; i < M; ++i)a[X[i]] = W[i]; vector<ll> dp(N+1); //dp[0] = a[0]; segtree st, st2; st.init(N+1); st2.init(N+1); st2.set(0, dp[0]); for (int i = 1; i < N; ++i) { ll mx = 0ll, mx2 = 0ll; if (i-2 >= 0)mx = st.get(0, i-1), mx2 = st2.get(0, i-1); if (i+1 < N) { st2.set(i, st.get(0, i)+a[i]); } dp[i] = max(mx, mx2)+a[i]; st.set(i, dp[i]); } return max(st.tree[0], st2.tree[0]); } //int main() { //int n, m; //cin >> n >> m; //vector<int> x(m), y(m), w(m); //for (int i = 0; i < m; ++i)cin >> x[i] >> y[i] >> w[i]; //cout << max_weights(n, m, x, y, w); //}
#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...