답안 #335928

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
335928	2020-12-14T10:11:52 Z	Vladth11	Discharging (NOI20_discharging)	C++14	100 / 100	293 ms	89040 KB

Discharging

#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debug_with_space(x) cerr << #x << " " << x << " "

using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <ll, pii> piii;

const ll NMAX = 1000001;
const ll INF = (1LL << 60);
const ll MOD = 1000000007;
const ll BLOCK = 101;
const ll nr_of_bits = 35;

struct functie{
    ll a, b;
    ll valoare(ll x){
        return a * x + b;
    }
};

functie tree[NMAX * 4];

void update(ll node, ll st, ll dr, functie x){
    if(st == dr){
        if(x.valoare(st) < tree[node].valoare(st)){
            swap(x, tree[node]);
        }
        return;
    }
    ll mid = (st + dr) / 2;
    ll xs = x.valoare(st);
    ll xm = x.valoare(mid);
    ll ts = tree[node].valoare(st);
    ll tm = tree[node].valoare(mid);
    if(xm < tm){
        if(xs < ts){
            swap(tree[node], x);
            update(node * 2 + 1, mid + 1, dr, x);
        }else{
            swap(tree[node], x);
            update(node * 2, st, mid, x);
        }
    }else{
        if(xs < ts){
            update(node * 2, st, mid, x);
        }else{
            update(node * 2 + 1, mid + 1, dr, x);
        }
    }
}

ll query(ll node, ll st, ll dr, ll col){
    if(st == dr){
        return tree[node].valoare(col);
    }
    ll mid = (st + dr) / 2;
    ll val = tree[node].valoare(col);
    if(col <= mid){
        return min(query(node * 2, st, mid, col), val);
    }else{
        return min(val, query(node * 2 + 1, mid + 1, dr, col));
    }
}

vector <pii> grupe;
ll dp[NMAX + 1];
ll v[NMAX];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    for(ll i = 0; i < 4 * NMAX; i++){
        tree[i].b = INF;
    }
    ll n, i, ind = 1;
    cin >> n;
    cin >> v[1];
    for(i = 2; i <= n; i++){
        cin >> v[i];
        if(v[i] > v[ind]){
            grupe.push_back({v[ind], ind});
            ind = i;
        }
    }
    grupe.push_back({v[ind], ind});
    dp[grupe.size() + 1] = 0;
    n++;
    for(i = grupe.size() ; i >= 1; i--){
        update(1, 1, n, {grupe[i - 1].first, dp[i + 1]});
        dp[i] = query(1, 1, n, (n - grupe[i - 1].second + 1 - 1));
    }
    cout << dp[1];
    return 0;
}

Subtask #1
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	37 ms	62956 KB	Output is correct
2	Correct	36 ms	62956 KB	Output is correct
3	Correct	36 ms	63084 KB	Output is correct
4	Correct	37 ms	62956 KB	Output is correct
5	Correct	36 ms	62956 KB	Output is correct
6	Correct	39 ms	62956 KB	Output is correct
7	Correct	39 ms	62956 KB	Output is correct
8	Correct	36 ms	62956 KB	Output is correct
9	Correct	36 ms	63084 KB	Output is correct
10	Correct	38 ms	62956 KB	Output is correct
11	Correct	39 ms	62956 KB	Output is correct
12	Correct	42 ms	62956 KB	Output is correct
13	Correct	37 ms	62992 KB	Output is correct
14	Correct	37 ms	62976 KB	Output is correct

Subtask #2
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	37 ms	63084 KB	Output is correct
2	Correct	37 ms	63084 KB	Output is correct
3	Correct	37 ms	63084 KB	Output is correct
4	Correct	38 ms	63084 KB	Output is correct
5	Correct	37 ms	63084 KB	Output is correct
6	Correct	38 ms	63160 KB	Output is correct
7	Correct	37 ms	63084 KB	Output is correct
8	Correct	37 ms	63084 KB	Output is correct
9	Correct	37 ms	63084 KB	Output is correct
10	Correct	37 ms	63084 KB	Output is correct
11	Correct	38 ms	63084 KB	Output is correct
12	Correct	37 ms	63084 KB	Output is correct
13	Correct	36 ms	63044 KB	Output is correct
14	Correct	37 ms	63104 KB	Output is correct
15	Correct	38 ms	63096 KB	Output is correct

Subtask #3
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	37 ms	63084 KB	Output is correct
2	Correct	37 ms	63084 KB	Output is correct
3	Correct	37 ms	63084 KB	Output is correct
4	Correct	38 ms	63084 KB	Output is correct
5	Correct	37 ms	63084 KB	Output is correct
6	Correct	38 ms	63160 KB	Output is correct
7	Correct	37 ms	63084 KB	Output is correct
8	Correct	37 ms	63084 KB	Output is correct
9	Correct	37 ms	63084 KB	Output is correct
10	Correct	37 ms	63084 KB	Output is correct
11	Correct	38 ms	63084 KB	Output is correct
12	Correct	37 ms	63084 KB	Output is correct
13	Correct	36 ms	63044 KB	Output is correct
14	Correct	37 ms	63104 KB	Output is correct
15	Correct	38 ms	63096 KB	Output is correct
16	Correct	225 ms	81692 KB	Output is correct
17	Correct	238 ms	83152 KB	Output is correct
18	Correct	211 ms	80476 KB	Output is correct
19	Correct	278 ms	83024 KB	Output is correct
20	Correct	242 ms	84304 KB	Output is correct
21	Correct	260 ms	83280 KB	Output is correct
22	Correct	226 ms	82256 KB	Output is correct
23	Correct	276 ms	88528 KB	Output is correct
24	Correct	259 ms	89040 KB	Output is correct
25	Correct	260 ms	89040 KB	Output is correct
26	Correct	293 ms	88016 KB	Output is correct
27	Correct	236 ms	80848 KB	Output is correct
28	Correct	237 ms	83712 KB	Output is correct
29	Correct	259 ms	88912 KB	Output is correct
30	Correct	287 ms	88272 KB	Output is correct

Subtask #4
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	149 ms	72312 KB	Output is correct
2	Correct	154 ms	72556 KB	Output is correct
3	Correct	150 ms	72556 KB	Output is correct
4	Correct	150 ms	72556 KB	Output is correct
5	Correct	151 ms	72512 KB	Output is correct
6	Correct	150 ms	72684 KB	Output is correct
7	Correct	151 ms	72624 KB	Output is correct
8	Correct	153 ms	72684 KB	Output is correct
9	Correct	149 ms	72532 KB	Output is correct
10	Correct	148 ms	72652 KB	Output is correct

Subtask #5
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	37 ms	62956 KB	Output is correct
2	Correct	36 ms	62956 KB	Output is correct
3	Correct	36 ms	63084 KB	Output is correct
4	Correct	37 ms	62956 KB	Output is correct
5	Correct	36 ms	62956 KB	Output is correct
6	Correct	39 ms	62956 KB	Output is correct
7	Correct	39 ms	62956 KB	Output is correct
8	Correct	36 ms	62956 KB	Output is correct
9	Correct	36 ms	63084 KB	Output is correct
10	Correct	38 ms	62956 KB	Output is correct
11	Correct	39 ms	62956 KB	Output is correct
12	Correct	42 ms	62956 KB	Output is correct
13	Correct	37 ms	62992 KB	Output is correct
14	Correct	37 ms	62976 KB	Output is correct
15	Correct	37 ms	63084 KB	Output is correct
16	Correct	37 ms	63084 KB	Output is correct
17	Correct	37 ms	63084 KB	Output is correct
18	Correct	38 ms	63084 KB	Output is correct
19	Correct	37 ms	63084 KB	Output is correct
20	Correct	38 ms	63160 KB	Output is correct
21	Correct	37 ms	63084 KB	Output is correct
22	Correct	37 ms	63084 KB	Output is correct
23	Correct	37 ms	63084 KB	Output is correct
24	Correct	37 ms	63084 KB	Output is correct
25	Correct	38 ms	63084 KB	Output is correct
26	Correct	37 ms	63084 KB	Output is correct
27	Correct	36 ms	63044 KB	Output is correct
28	Correct	37 ms	63104 KB	Output is correct
29	Correct	38 ms	63096 KB	Output is correct
30	Correct	37 ms	62956 KB	Output is correct
31	Correct	37 ms	62956 KB	Output is correct
32	Correct	37 ms	62956 KB	Output is correct
33	Correct	37 ms	62956 KB	Output is correct
34	Correct	37 ms	62956 KB	Output is correct
35	Correct	37 ms	62956 KB	Output is correct
36	Correct	36 ms	62956 KB	Output is correct
37	Correct	36 ms	62956 KB	Output is correct
38	Correct	37 ms	62956 KB	Output is correct
39	Correct	36 ms	62956 KB	Output is correct
40	Correct	36 ms	62956 KB	Output is correct
41	Correct	36 ms	62956 KB	Output is correct
42	Correct	37 ms	62956 KB	Output is correct
43	Correct	37 ms	63084 KB	Output is correct
44	Correct	37 ms	62956 KB	Output is correct
45	Correct	37 ms	62956 KB	Output is correct
46	Correct	37 ms	62956 KB	Output is correct
47	Correct	39 ms	62956 KB	Output is correct
48	Correct	37 ms	62956 KB	Output is correct
49	Correct	37 ms	62956 KB	Output is correct
50	Correct	37 ms	62956 KB	Output is correct

Subtask #6
28.0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	37 ms	62956 KB	Output is correct
2	Correct	36 ms	62956 KB	Output is correct
3	Correct	36 ms	63084 KB	Output is correct
4	Correct	37 ms	62956 KB	Output is correct
5	Correct	36 ms	62956 KB	Output is correct
6	Correct	39 ms	62956 KB	Output is correct
7	Correct	39 ms	62956 KB	Output is correct
8	Correct	36 ms	62956 KB	Output is correct
9	Correct	36 ms	63084 KB	Output is correct
10	Correct	38 ms	62956 KB	Output is correct
11	Correct	39 ms	62956 KB	Output is correct
12	Correct	42 ms	62956 KB	Output is correct
13	Correct	37 ms	62992 KB	Output is correct
14	Correct	37 ms	62976 KB	Output is correct
15	Correct	37 ms	63084 KB	Output is correct
16	Correct	37 ms	63084 KB	Output is correct
17	Correct	37 ms	63084 KB	Output is correct
18	Correct	38 ms	63084 KB	Output is correct
19	Correct	37 ms	63084 KB	Output is correct
20	Correct	38 ms	63160 KB	Output is correct
21	Correct	37 ms	63084 KB	Output is correct
22	Correct	37 ms	63084 KB	Output is correct
23	Correct	37 ms	63084 KB	Output is correct
24	Correct	37 ms	63084 KB	Output is correct
25	Correct	38 ms	63084 KB	Output is correct
26	Correct	37 ms	63084 KB	Output is correct
27	Correct	36 ms	63044 KB	Output is correct
28	Correct	37 ms	63104 KB	Output is correct
29	Correct	38 ms	63096 KB	Output is correct
30	Correct	225 ms	81692 KB	Output is correct
31	Correct	238 ms	83152 KB	Output is correct
32	Correct	211 ms	80476 KB	Output is correct
33	Correct	278 ms	83024 KB	Output is correct
34	Correct	242 ms	84304 KB	Output is correct
35	Correct	260 ms	83280 KB	Output is correct
36	Correct	226 ms	82256 KB	Output is correct
37	Correct	276 ms	88528 KB	Output is correct
38	Correct	259 ms	89040 KB	Output is correct
39	Correct	260 ms	89040 KB	Output is correct
40	Correct	293 ms	88016 KB	Output is correct
41	Correct	236 ms	80848 KB	Output is correct
42	Correct	237 ms	83712 KB	Output is correct
43	Correct	259 ms	88912 KB	Output is correct
44	Correct	287 ms	88272 KB	Output is correct
45	Correct	149 ms	72312 KB	Output is correct
46	Correct	154 ms	72556 KB	Output is correct
47	Correct	150 ms	72556 KB	Output is correct
48	Correct	150 ms	72556 KB	Output is correct
49	Correct	151 ms	72512 KB	Output is correct
50	Correct	150 ms	72684 KB	Output is correct
51	Correct	151 ms	72624 KB	Output is correct
52	Correct	153 ms	72684 KB	Output is correct
53	Correct	149 ms	72532 KB	Output is correct
54	Correct	148 ms	72652 KB	Output is correct
55	Correct	37 ms	62956 KB	Output is correct
56	Correct	37 ms	62956 KB	Output is correct
57	Correct	37 ms	62956 KB	Output is correct
58	Correct	37 ms	62956 KB	Output is correct
59	Correct	37 ms	62956 KB	Output is correct
60	Correct	37 ms	62956 KB	Output is correct
61	Correct	36 ms	62956 KB	Output is correct
62	Correct	36 ms	62956 KB	Output is correct
63	Correct	37 ms	62956 KB	Output is correct
64	Correct	36 ms	62956 KB	Output is correct
65	Correct	36 ms	62956 KB	Output is correct
66	Correct	36 ms	62956 KB	Output is correct
67	Correct	37 ms	62956 KB	Output is correct
68	Correct	37 ms	63084 KB	Output is correct
69	Correct	37 ms	62956 KB	Output is correct
70	Correct	37 ms	62956 KB	Output is correct
71	Correct	37 ms	62956 KB	Output is correct
72	Correct	39 ms	62956 KB	Output is correct
73	Correct	37 ms	62956 KB	Output is correct
74	Correct	37 ms	62956 KB	Output is correct
75	Correct	37 ms	62956 KB	Output is correct
76	Correct	129 ms	72428 KB	Output is correct
77	Correct	130 ms	72428 KB	Output is correct
78	Correct	126 ms	72556 KB	Output is correct
79	Correct	127 ms	72556 KB	Output is correct
80	Correct	134 ms	72428 KB	Output is correct
81	Correct	126 ms	72556 KB	Output is correct
82	Correct	125 ms	72556 KB	Output is correct
83	Correct	128 ms	72428 KB	Output is correct
84	Correct	127 ms	72556 KB	Output is correct
85	Correct	131 ms	72576 KB	Output is correct
86	Correct	126 ms	72556 KB	Output is correct
87	Correct	125 ms	72556 KB	Output is correct
88	Correct	125 ms	72480 KB	Output is correct
89	Correct	127 ms	72464 KB	Output is correct
90	Correct	125 ms	72556 KB	Output is correct
91	Correct	124 ms	72556 KB	Output is correct
92	Correct	251 ms	84968 KB	Output is correct
93	Correct	232 ms	83152 KB	Output is correct
94	Correct	124 ms	72300 KB	Output is correct
95	Correct	130 ms	72044 KB	Output is correct
96	Correct	123 ms	72116 KB	Output is correct
97	Correct	127 ms	72044 KB	Output is correct
98	Correct	127 ms	71916 KB	Output is correct
99	Correct	125 ms	71660 KB	Output is correct
100	Correct	128 ms	71532 KB	Output is correct

답안 #335928

Compilation message

Subtask #1 9.0 / 9.0

Subtask #2 13.0 / 13.0

Subtask #3 25.0 / 25.0

Subtask #4 11.0 / 11.0

Subtask #5 14.0 / 14.0

Subtask #6 28.0 / 28.0

Subtask #1
9.0 / 9.0

Subtask #2
13.0 / 13.0

Subtask #3
25.0 / 25.0

Subtask #4
11.0 / 11.0

Subtask #5
14.0 / 14.0

Subtask #6
28.0 / 28.0