Submission #677665

#TimeUsernameProblemLanguageResultExecution timeMemory
677665Cross_RatioSeesaw (JOI22_seesaw)C++14
67 / 100
187 ms28760 KiB
#include <bits/stdc++.h> #define int long long using namespace std; int A[200005]; int B[200005]; int N; vector<double> V[200005]; int sum(int x, int y) { return B[y] - (x?B[x-1]:0); } typedef pair<int,int> P; typedef pair<double, pair<int,int>> PP; signed main() { cin.sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> N; int i, j; for(i=0;i<N;i++) cin >> A[i]; for(i=0;i<N;i++) { B[i] = (i?B[i-1]:0)+A[i]; } int s1 = 0, e1 = N-1, s2 = 0, e2 = N-1; V[N].push_back((double)B[N-1]/N); for(i=N-1;i>=1;i--) { if(sum(s1+1, e1)*N < B[N-1]*i) { s1++; } else e1--; if(sum(s2, e2-1)*N > B[N-1]*i) { e2--; } else s2++; for(j=s1;j<=s2;j++) { V[i].push_back((double)sum(j, j+i-1) / i); } } set<PP> S; for(i=1;i<=N;i++) { S.insert(PP(V[i][0], P(i, 0))); } double ans = 1e9; while(true) { double mi = S.begin()->first; double ma = S.rbegin()->first; ans = min(ans, ma - mi); PP k = *S.begin(); auto it = S.begin(); S.erase(it); int k1 = k.second.first, k2 = k.second.second; if(k2+1>=V[k1].size()) break; S.insert(PP(V[k1][k2+1], P(k1, k2))); } cout << fixed << setprecision(15) << ans; }

Compilation message (stderr)

seesaw.cpp: In function 'int main()':
seesaw.cpp:51:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         if(k2+1>=V[k1].size()) break;
      |            ~~~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...