oj.uz

Submission #688577

# Submission time Handle Problem Language Result Execution time Memory
688577 2023-01-27T18:27:35 Z ksjsjsjsjsjsjs Discharging (NOI20_discharging) C++17
100 / 100
 518 ms 291124 KB 
#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define _pb pop_back
#define _pf pop_front
#define lb lower_bound
#define ub upper_bound
#define bg begin
#define ed end
#define ins insert
#define ers erase
#define mtp make_tuple
#define sz(x) (int)(x).size()
#define all(x) (x).bg(), (x).ed
#define ft front
#define bk back
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define str string
#define pi pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vll vector<ll>
#define vpi vector<pi>
#define vpll vector<pll>
#define FOR(i, l, r) for (int i = (l); i <= (r); ++i)
#define FOS(i, r, l) for (int i = (r); i >= (l); --i)
#define FRN(i, n) for (int i = 0; i < (n); ++i)
#define FSN(i, n) for (int i = (n) - 1; i >= 0; --i)
#define EACH(i, x) for (auto &i : (x))
#define WHILE while
template<typename T> T gcd(T a, T b) { WHILE(b) { a %= b; swap(a, b); } return a; }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
#define file "TEST"
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rd); }
struct Save {
    int i;
    pll v;
    Save() {}
    Save(int i, pll v) : i(i), v(v) {}
};
const int oo = 1e9 + 5;
const int T = 4e6 + 5;
const int N = 1e6 + 5;
const pll df = {0, 1e18};
int n, t[N], cnt[N];
ll d[N], d1[N];
ll cost(int i, pll d) { return 1LL * d.st * i + d.nd; }
pll tr[T];
vector<Save> s;
void upd(int i, int l, int r, pll v) {
    int mid = l + (r - l) / 2;
    if (cost(mid, v) < cost(mid, tr[i])) {
        s.pb(Save(i, tr[i]));
        swap(tr[i], v);
    }
    if (l == r) return;
    if (cost(l, tr[i]) > cost(l, v)) upd(i * 2, l, mid, v);
    else upd(i * 2 + 1, mid + 1, r, v);
}
ll get(int i, int l, int r, int q) {
    ll rs = cost(q, tr[i]);
    int mid = l + (r - l) / 2;
    if (l == r) return rs;
    if (q <= mid) rs = min(rs, get(i * 2, l, mid, q));
    else rs = min(rs, get(i * 2 + 1, mid + 1, r, q));
    return rs;
}
void roll(int cnt) {
    FRN(i, cnt) {
        tr[s.bk().i] = s.bk().v;
        s._pb();
    }
}
signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//    freopen(file".inp", "r", stdin);
//    freopen(file".out", "w", stdout);
//    s.resize(2e7);
//    s.clear();
    cin >> n;
    FOR(i, 1, n) cin >> t[i];
    int pos = 0;
    FOR(i, 1, n << 2) tr[i] = df;
    deque<int> d2;
    FOS(i, n, 1) {
        WHILE(!d2.empty() && t[d2.bk()] <= t[i]) {
            roll(cnt[d2.bk()]);
            d2._pb();
        }
        d1[i] = 1LL * (n - i + 1) * t[i] + (d2.empty()? 0 : d[d2.bk()]);
        d2.pb(i);
        int pre = sz(s);
        upd(1, 1, n, {-t[i], d1[i] + 1LL * i * t[i]});
        cnt[i] = sz(s) - pre;
        d[i] = get(1, 1, n, i);
    }
    cout << d[1];
//    cerr << "\nTime: " << setprecision(5) << fixed << (ldb)clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}
/*
*/

Compilation message

Discharging.cpp: In function 'int main()':
Discharging.cpp:89:9: warning: unused variable 'pos' [-Wunused-variable]
   89 |     int pos = 0;
      |         ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 332 KB Output is correct
14 Correct 0 ms 336 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 792 KB Output is correct
4 Correct 1 ms 728 KB Output is correct
5 Correct 1 ms 792 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 792 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 476 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 724 KB Output is correct
13 Correct 1 ms 724 KB Output is correct
14 Correct 1 ms 792 KB Output is correct
15 Correct 1 ms 800 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 792 KB Output is correct
4 Correct 1 ms 728 KB Output is correct
5 Correct 1 ms 792 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 792 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 476 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 724 KB Output is correct
13 Correct 1 ms 724 KB Output is correct
14 Correct 1 ms 792 KB Output is correct
15 Correct 1 ms 800 KB Output is correct
16 Correct 476 ms 275056 KB Output is correct
17 Correct 483 ms 275832 KB Output is correct
18 Correct 502 ms 274288 KB Output is correct
19 Correct 482 ms 276336 KB Output is correct
20 Correct 497 ms 275664 KB Output is correct
21 Correct 479 ms 275588 KB Output is correct
22 Correct 502 ms 275436 KB Output is correct
23 Correct 498 ms 291068 KB Output is correct
24 Correct 494 ms 275764 KB Output is correct
25 Correct 488 ms 276292 KB Output is correct
26 Correct 501 ms 291124 KB Output is correct
27 Correct 469 ms 275024 KB Output is correct
28 Correct 481 ms 275756 KB Output is correct
29 Correct 495 ms 276316 KB Output is correct
30 Correct 518 ms 289340 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 95984 KB Output is correct
2 Correct 280 ms 96052 KB Output is correct
3 Correct 281 ms 96064 KB Output is correct
4 Correct 279 ms 96068 KB Output is correct
5 Correct 281 ms 96232 KB Output is correct
6 Correct 275 ms 96028 KB Output is correct
7 Correct 285 ms 96100 KB Output is correct
8 Correct 283 ms 96052 KB Output is correct
9 Correct 295 ms 96012 KB Output is correct
10 Correct 313 ms 96096 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 332 KB Output is correct
14 Correct 0 ms 336 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 724 KB Output is correct
17 Correct 1 ms 792 KB Output is correct
18 Correct 1 ms 728 KB Output is correct
19 Correct 1 ms 792 KB Output is correct
20 Correct 1 ms 724 KB Output is correct
21 Correct 1 ms 792 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 1 ms 476 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 1 ms 468 KB Output is correct
26 Correct 1 ms 724 KB Output is correct
27 Correct 1 ms 724 KB Output is correct
28 Correct 1 ms 792 KB Output is correct
29 Correct 1 ms 800 KB Output is correct
30 Correct 1 ms 468 KB Output is correct
31 Correct 1 ms 472 KB Output is correct
32 Correct 2 ms 468 KB Output is correct
33 Correct 1 ms 468 KB Output is correct
34 Correct 1 ms 468 KB Output is correct
35 Correct 1 ms 468 KB Output is correct
36 Correct 1 ms 468 KB Output is correct
37 Correct 1 ms 468 KB Output is correct
38 Correct 1 ms 468 KB Output is correct
39 Correct 2 ms 468 KB Output is correct
40 Correct 1 ms 472 KB Output is correct
41 Correct 1 ms 468 KB Output is correct
42 Correct 1 ms 472 KB Output is correct
43 Correct 2 ms 724 KB Output is correct
44 Correct 1 ms 440 KB Output is correct
45 Correct 1 ms 468 KB Output is correct
46 Correct 1 ms 468 KB Output is correct
47 Correct 1 ms 468 KB Output is correct
48 Correct 1 ms 472 KB Output is correct
49 Correct 1 ms 468 KB Output is correct
50 Correct 1 ms 468 KB Output is correct

Subtask #6
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 332 KB Output is correct
14 Correct 0 ms 336 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 724 KB Output is correct
17 Correct 1 ms 792 KB Output is correct
18 Correct 1 ms 728 KB Output is correct
19 Correct 1 ms 792 KB Output is correct
20 Correct 1 ms 724 KB Output is correct
21 Correct 1 ms 792 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 1 ms 476 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 1 ms 468 KB Output is correct
26 Correct 1 ms 724 KB Output is correct
27 Correct 1 ms 724 KB Output is correct
28 Correct 1 ms 792 KB Output is correct
29 Correct 1 ms 800 KB Output is correct
30 Correct 476 ms 275056 KB Output is correct
31 Correct 483 ms 275832 KB Output is correct
32 Correct 502 ms 274288 KB Output is correct
33 Correct 482 ms 276336 KB Output is correct
34 Correct 497 ms 275664 KB Output is correct
35 Correct 479 ms 275588 KB Output is correct
36 Correct 502 ms 275436 KB Output is correct
37 Correct 498 ms 291068 KB Output is correct
38 Correct 494 ms 275764 KB Output is correct
39 Correct 488 ms 276292 KB Output is correct
40 Correct 501 ms 291124 KB Output is correct
41 Correct 469 ms 275024 KB Output is correct
42 Correct 481 ms 275756 KB Output is correct
43 Correct 495 ms 276316 KB Output is correct
44 Correct 518 ms 289340 KB Output is correct
45 Correct 289 ms 95984 KB Output is correct
46 Correct 280 ms 96052 KB Output is correct
47 Correct 281 ms 96064 KB Output is correct
48 Correct 279 ms 96068 KB Output is correct
49 Correct 281 ms 96232 KB Output is correct
50 Correct 275 ms 96028 KB Output is correct
51 Correct 285 ms 96100 KB Output is correct
52 Correct 283 ms 96052 KB Output is correct
53 Correct 295 ms 96012 KB Output is correct
54 Correct 313 ms 96096 KB Output is correct
55 Correct 1 ms 468 KB Output is correct
56 Correct 1 ms 472 KB Output is correct
57 Correct 2 ms 468 KB Output is correct
58 Correct 1 ms 468 KB Output is correct
59 Correct 1 ms 468 KB Output is correct
60 Correct 1 ms 468 KB Output is correct
61 Correct 1 ms 468 KB Output is correct
62 Correct 1 ms 468 KB Output is correct
63 Correct 1 ms 468 KB Output is correct
64 Correct 2 ms 468 KB Output is correct
65 Correct 1 ms 472 KB Output is correct
66 Correct 1 ms 468 KB Output is correct
67 Correct 1 ms 472 KB Output is correct
68 Correct 2 ms 724 KB Output is correct
69 Correct 1 ms 440 KB Output is correct
70 Correct 1 ms 468 KB Output is correct
71 Correct 1 ms 468 KB Output is correct
72 Correct 1 ms 468 KB Output is correct
73 Correct 1 ms 472 KB Output is correct
74 Correct 1 ms 468 KB Output is correct
75 Correct 1 ms 468 KB Output is correct
76 Correct 369 ms 92384 KB Output is correct
77 Correct 366 ms 92440 KB Output is correct
78 Correct 362 ms 91768 KB Output is correct
79 Correct 349 ms 92068 KB Output is correct
80 Correct 373 ms 92756 KB Output is correct
81 Correct 358 ms 91908 KB Output is correct
82 Correct 356 ms 91920 KB Output is correct
83 Correct 362 ms 92364 KB Output is correct
84 Correct 361 ms 92132 KB Output is correct
85 Correct 347 ms 92484 KB Output is correct
86 Correct 342 ms 91896 KB Output is correct
87 Correct 329 ms 91804 KB Output is correct
88 Correct 364 ms 92148 KB Output is correct
89 Correct 390 ms 91892 KB Output is correct
90 Correct 358 ms 91876 KB Output is correct
91 Correct 324 ms 91672 KB Output is correct
92 Correct 496 ms 276964 KB Output is correct
93 Correct 487 ms 275736 KB Output is correct
94 Correct 320 ms 91340 KB Output is correct
95 Correct 341 ms 92792 KB Output is correct
96 Correct 325 ms 91592 KB Output is correct
97 Correct 320 ms 92024 KB Output is correct
98 Correct 327 ms 92108 KB Output is correct
99 Correct 324 ms 91860 KB Output is correct
100 Correct 336 ms 91944 KB Output is correct