Submission #467323

#TimeUsernameProblemLanguageResultExecution timeMemory
467323ivan_tudorHoliday (IOI14_holiday)C++17
0 / 100
5074 ms5668 KiB
#include"holiday.h" #include<bits/stdc++.h> using namespace std; const int N = 100005; int a[N]; multiset<long long> big, small; long long sum; int canhold; int L, R; void insert_val(int v){ big.insert(v); sum += v; while((int)big.size() > max(canhold, 0)){ int lval = (*big.begin()); sum -= *big.begin(); big.erase(*big.begin()); small.insert(*big.begin()); } } void erase_val(int v){ if(small.count(v)){ small.erase(small.find(v)); } else if(big.count(v)){ big.erase(big.find(v)); sum -= v; } while((int)big.size() < canhold && small.size() > 0){ int val = (*small.rbegin()); big.insert(*small.rbegin()); sum += *small.rbegin(); small.erase(*small.rbegin()); } } long long op = 0; void transf(int newL, int newR){ while(L > newL){ canhold -=2; L--; insert_val(a[L]); op++; } while(R < newR){ canhold --; R++; insert_val(a[R]); op++; } while(L < newL){ canhold +=2; erase_val(a[L]); L++; op++; } while(R > newR){ canhold++; erase_val(a[R]); R--; op++; } } long long ans = 0; void solve(int l, int r, int opl, int opr){ if(r < l) return; int mid = (l + r)/2; long long maxi = -1, mpoz; for(int i = max(opl, mid); i <= opr; i++){ transf(mid, i); if(canhold <= 0) break; if(maxi < sum){ maxi = sum; mpoz = i; } } ans = max(ans, maxi); if(l == r) return; if(l <= mid - 1) solve(l, mid - 1, opl, mpoz); if(mid + 1 <= r) solve(mid + 1, r, mpoz, opr); } long long int findMaxAttraction(int n, int start, int d, int attraction[]) { for(int i = 0; i < n; i++) a[i] = attraction[i]; sum = 0; L = R = start; canhold = d; insert_val(a[start]); solve(0, start, start, n - 1); reverse(a, a+n); start = n - 1 - start; big.clear(); small.clear(); sum = 0; L = R = start; canhold = d; insert_val(a[start]); solve(0, start, start, n - 1); // cerr<<op;*/ return ans; }

Compilation message (stderr)

holiday.cpp: In function 'void insert_val(int)':
holiday.cpp:14:9: warning: unused variable 'lval' [-Wunused-variable]
   14 |     int lval = (*big.begin());
      |         ^~~~
holiday.cpp: In function 'void erase_val(int)':
holiday.cpp:30:9: warning: unused variable 'val' [-Wunused-variable]
   30 |     int val = (*small.rbegin());
      |         ^~~
holiday.cpp: In function 'void solve(int, int, int, int)':
holiday.cpp:85:10: warning: 'mpoz' may be used uninitialized in this function [-Wmaybe-uninitialized]
   85 |     solve(mid + 1, r, mpoz, opr);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...