Submission #1217387

#TimeUsernameProblemLanguageResultExecution timeMemory
1217387dostsNile (IOI24_nile)C++20
67 / 100
2095 ms6468 KiB
#include "nile.h" #include <bits/stdc++.h> #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2") #define int long long #define pii pair<int,int> #define vi vector<int> #define ff first #define ss second #define sp << " " << #define all(x) x.begin(),x.end() #define big(x) ((int)(x.size())) using namespace std; const int MOD = 1e9+7, LIM = 1e6+1, inf = 2e9; std::vector<long long> calculate_costs(std::vector<signed> W, std::vector<signed> A, std::vector<signed> B, std::vector<signed> E) { int Q = big(E); int N = big(W); vi inds(N); iota(all(inds),0ll); sort(all(inds),[&](int x,int y) {return W[x] < W[y];}); vi benefit(N); int sm = 0; for (int i = 0;i<N;i++) { sm+=A[inds[i]]; benefit[i] = A[inds[i]]-B[inds[i]]; } std::vector<long long> R(Q, 0); for (int ii = 0;ii<Q;ii++) { int D = E[ii]; vi dp(N,0); dp[0] = 0; for (int i=1;i<N;i++) { dp[i] = dp[i-1]; if (W[inds[i]]-W[inds[i-1]] <= D) { if (i == 1) dp[i] = max(dp[i],benefit[i]+benefit[i-1]); else dp[i] = max(dp[i],benefit[i]+benefit[i-1]+dp[i-2]); } if (i>=2 && W[inds[i]]-W[inds[i-2]] <= D) { dp[i] = max(dp[i],benefit[i]+benefit[i-2]+((i>2)?dp[i-3]:0ll)); } } R[ii] = sm-dp[N-1]; } return R; }
#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...