Submission #612307

#TimeUsernameProblemLanguageResultExecution timeMemory
6123078e7Seesaw (JOI22_seesaw)C++17
67 / 100
206 ms54144 KiB
//Challenge: Accepted #pragma GCC optimize("Ofast") #include <bits/stdc++.h> using namespace std; #ifdef zisk void debug(){cout << endl;} template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);} template<class T> void pary(T l, T r) { while (l != r) cout << *l << " ", l++; cout << endl; } #else #define debug(...) 0 #define pary(...) 0 #endif #define ll long long #define double long double #define maxn 2005 #define pii pair<ll, ll> #define ff first #define ss second #define io ios_base::sync_with_stdio(0);cin.tie(0); const ll inf = 1LL<<50; struct frac{ ll f, s, id; frac(){f = s = id = 0;} frac(ll a, ll b, ll c){f = a, s = b, id = c;} bool operator <(const frac &p) { return f * p.s < s * p.f; } }; bool cmp(const frac &p, const frac &q){ return p.f * q.s > p.s * q.f; } frac operator -(frac &p, frac &q){ return frac(p.f * q.s - q.f * p.s, p.s * q.s, 0); } vector<frac> a[maxn]; ll ind[maxn], p[maxn], pref[maxn]; int main() { io int n; cin >> n; for (int i = 0;i < n;i++) { cin >> p[i]; pref[i] = p[i] + (i ? pref[i-1] : 0); } priority_queue<frac, vector<frac>, bool (*) (const frac&, const frac&) > pq(cmp); frac ma(0, 1, 0); for (int x = 0;x < n;x++) { for (int i = 0;i < x + 1;i++) { int j = i + n - 1 - x; //[i, j] a[x].push_back(frac(pref[j] - (i ? pref[i-1] : 0), n - x, x)); if (i == 0) { pq.push(a[x].back()); if (ma < a[x].back()) ma = a[x].back(); } } } frac ans(inf, 1, 0); while (pq.size()) { frac cur = pq.top();pq.pop(); //debug(cur.f, cur.s, cur.id, ma.f, ma.s); frac val = ma - cur; if (val < ans) ans = val; ind[cur.id]++; if (ind[cur.id] < a[cur.id].size()) { frac add = a[cur.id][ind[cur.id]]; if (ma < add) ma = add; pq.push(add); } else { break; } } double out = ((double)ans.f) / ans.s; cout << fixed << setprecision(15) << out << "\n"; }

Compilation message (stderr)

seesaw.cpp: In function 'int main()':
seesaw.cpp:68:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<frac>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |   if (ind[cur.id] < a[cur.id].size()) {
      |       ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...