# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
494806 | 2021-12-16T14:59:40 Z | blue | Discharging (NOI20_discharging) | C++17 | 444 ms | 10012 KB |
#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
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 0 ms | 204 KB | Output is correct |
3 | Correct | 1 ms | 204 KB | Output is correct |
4 | Correct | 0 ms | 204 KB | Output is correct |
5 | Correct | 0 ms | 204 KB | Output is correct |
6 | Correct | 1 ms | 208 KB | Output is correct |
7 | Correct | 0 ms | 208 KB | Output is correct |
8 | Correct | 1 ms | 208 KB | Output is correct |
9 | Correct | 0 ms | 208 KB | Output is correct |
10 | Correct | 1 ms | 292 KB | Output is correct |
11 | Correct | 0 ms | 296 KB | Output is correct |
12 | Correct | 1 ms | 208 KB | Output is correct |
13 | Correct | 0 ms | 208 KB | Output is correct |
14 | Correct | 0 ms | 208 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 332 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 332 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 372 ms | 268 KB | Output is correct |
2 | Correct | 444 ms | 9820 KB | Output is correct |
3 | Correct | 405 ms | 9828 KB | Output is correct |
4 | Correct | 404 ms | 9808 KB | Output is correct |
5 | Correct | 379 ms | 9820 KB | Output is correct |
6 | Correct | 387 ms | 9832 KB | Output is correct |
7 | Correct | 405 ms | 9820 KB | Output is correct |
8 | Correct | 373 ms | 9956 KB | Output is correct |
9 | Correct | 397 ms | 10012 KB | Output is correct |
10 | Correct | 385 ms | 9820 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 0 ms | 204 KB | Output is correct |
3 | Correct | 1 ms | 204 KB | Output is correct |
4 | Correct | 0 ms | 204 KB | Output is correct |
5 | Correct | 0 ms | 204 KB | Output is correct |
6 | Correct | 1 ms | 208 KB | Output is correct |
7 | Correct | 0 ms | 208 KB | Output is correct |
8 | Correct | 1 ms | 208 KB | Output is correct |
9 | Correct | 0 ms | 208 KB | Output is correct |
10 | Correct | 1 ms | 292 KB | Output is correct |
11 | Correct | 0 ms | 296 KB | Output is correct |
12 | Correct | 1 ms | 208 KB | Output is correct |
13 | Correct | 0 ms | 208 KB | Output is correct |
14 | Correct | 0 ms | 208 KB | Output is correct |
15 | Incorrect | 1 ms | 332 KB | Output isn't correct |
16 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 0 ms | 204 KB | Output is correct |
3 | Correct | 1 ms | 204 KB | Output is correct |
4 | Correct | 0 ms | 204 KB | Output is correct |
5 | Correct | 0 ms | 204 KB | Output is correct |
6 | Correct | 1 ms | 208 KB | Output is correct |
7 | Correct | 0 ms | 208 KB | Output is correct |
8 | Correct | 1 ms | 208 KB | Output is correct |
9 | Correct | 0 ms | 208 KB | Output is correct |
10 | Correct | 1 ms | 292 KB | Output is correct |
11 | Correct | 0 ms | 296 KB | Output is correct |
12 | Correct | 1 ms | 208 KB | Output is correct |
13 | Correct | 0 ms | 208 KB | Output is correct |
14 | Correct | 0 ms | 208 KB | Output is correct |
15 | Incorrect | 1 ms | 332 KB | Output isn't correct |
16 | Halted | 0 ms | 0 KB | - |