Submission #494806

#TimeUsernameProblemLanguageResultExecution timeMemory
494806blueDischarging (NOI20_discharging)C++17
20 / 100
444 ms10012 KiB
#include <iostream> #include <vector> #include <algorithm> using namespace std; using ll = long long; using vll = vector<ll>; using pll = pair<ll, ll>; #define sz(x) int(x.size()) const ll INF = 1'000'000'000'000'000'000LL; int main() { int N; cin >> N; int TS = N; vector<pll> T; ll t1; cin >> t1; T.push_back({t1, 1}); for(int i = 2; i <= N; i++) { ll t; cin >> t; if(t <= T.back().first) T.back().second++; else T.push_back({t, 1}); } // for(auto t:T) cerr << t.first << "/" << t.second << " "; // cerr << '\n'; int ct = 0; vector<pll> S; for(auto t:T) { // cerr << "turn = " << ++ct << '\n'; S.push_back(t); while(sz(S) >= 2) { auto x = S[sz(S)-2]; auto y = S[sz(S)-1]; // cerr << x.first << ' ' << x.second << " + " << y.first << ' ' << y.second << '\n'; // cerr << y.first * x.second << ' ' << x.first * (x.second + y.second) << '\n'; if(!(y.first * x.second <= x.first * (x.second + y.second))) break; // cerr << pll newT{S[sz(S)-1].first, S[sz(S)-1].second + S[sz(S)-2].second}; S.pop_back(); S.pop_back(); S.push_back(newT); } } // for(auto t:T) cerr << t.first << "/" << t.second << " "; // cerr << '\n'; ll ans = 0; reverse(S.begin(), S.end()); ll suff = 0; for(auto t:S) { suff += t.second; ans += suff*t.first; } cout << ans << '\n'; }

Compilation message (stderr)

Discharging.cpp: In function 'int main()':
Discharging.cpp:19:9: warning: unused variable 'TS' [-Wunused-variable]
   19 |     int TS = N;
      |         ^~
Discharging.cpp:38:9: warning: unused variable 'ct' [-Wunused-variable]
   38 |     int ct = 0;
      |         ^~
#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...