Submission #979915

#TimeUsernameProblemLanguageResultExecution timeMemory
979915SmuggingSpunRice Hub (IOI11_ricehub)C++14
17 / 100
226 ms7344 KiB
#include "ricehub.h" #include<bits/stdc++.h> using namespace std; typedef long long ll; template<class T>void maximize(T& a, T b){ if(a < b){ a = b; } } const int lim = 1e5 + 5; int N = 1, ans = 0, cnt[lim], to_X[lim]; map<int, int>X_to; ll sum[lim]; ll get_value(int p, int range){ int P = lower_bound(to_X + 1, to_X + N + 1, to_X[p] - range) - to_X - 1; ll sum_left = 1LL * to_X[p] * (cnt[p] - cnt[P]) - sum[p] + sum[P]; P = upper_bound(to_X + 1, to_X + N + 2, to_X[p] + range) - to_X - 1; return sum_left + sum[P] - sum[p] - 1LL * to_X[p] * (cnt[P] - cnt[p]); } int besthub(int n, int L, int X[], ll B){ memset(cnt, 0, sizeof(cnt)); memset(sum, 0, sizeof(sum)); X_to[to_X[1] = X[0]] = 1; for(int i = 0; i < n; i++){ if(i > 0 && X[i] != X[i - 1]){ X_to[to_X[++N] = X[i]] = N; } cnt[N]++; sum[N] += X[i]; } for(int i = 1; i <= N; i++){ cnt[i] += cnt[i - 1]; sum[i] += sum[i - 1]; } to_X[N + 1] = INT_MAX; for(int i = 1; i <= N; i++){ int low = 0, high = L, range; while(low <= high){ int mid = (low + high) >> 1; if(get_value(i, mid) <= B){ low = (range = mid) + 1; } else{ high = mid - 1; } } ll remain = B - get_value(i, range); map<int, int>::iterator it = X_to.find(to_X[i] - range - 1); int add_cnt = 0; if(it != X_to.end()){ int can_add = min(ll(cnt[it->second] - cnt[it->second - 1]), remain / (range + 1)); add_cnt += can_add; remain -= 1LL * can_add * range; } it = X_to.find(to_X[i] + range + 1); if(it != X_to.end()){ add_cnt += min(ll(cnt[it->second] - cnt[it->second - 1]), remain / (range + 1)); } maximize(ans, add_cnt + cnt[upper_bound(to_X + 1, to_X + N + 2, to_X[i] + range) - to_X - 1] - cnt[lower_bound(to_X + 1, to_X + N + 1, to_X[i] - range) - to_X - 1]); } return ans; }

Compilation message (stderr)

ricehub.cpp: In function 'int besthub(int, int, int*, ll)':
ricehub.cpp:26:14: warning: operation on 'N' may be undefined [-Wsequence-point]
   26 |    X_to[to_X[++N] = X[i]] = N;
      |              ^~~
ricehub.cpp:26:14: warning: operation on 'N' may be undefined [-Wsequence-point]
ricehub.cpp:48:50: warning: 'range' may be used uninitialized in this function [-Wmaybe-uninitialized]
   48 |   map<int, int>::iterator it = X_to.find(to_X[i] - range - 1);
      |                                          ~~~~~~~~^~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...