oj.uz

Submission #270357

# Submission time Handle Problem Language Result Execution time Memory
270357 2020-08-17T14:23:36 Z doowey Discharging (NOI20_discharging) C++14
36 / 100
 1000 ms 719220 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef long double ld;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

struct Line{
    ld ai;
    ld bi;
    ld ti;
};

ld intersect(Line t1, Line t2){
    return (t2.bi-t1.bi)/(t1.ai-t2.ai);
}

struct O{
    ll vv;
    deque<Line> hull;
    ll pf;
    void add_line(Line X){
        if(hull.empty()){
            hull.push_back(X);
        }
        else{
            while(hull.size() >= 2 && intersect(hull[hull.size() - 2], X) <= intersect(hull[hull.size() - 2], hull[hull.size() - 1])){
                hull.pop_back();
            }
            hull.push_back(X);

            hull[hull.size() - 2].ti = intersect(hull[hull.size() - 2], hull[hull.size() - 1]);
        }
    }
    ll getval(ll t){
        int li = 0, ri = (int)hull.size()-1;
        int mid;
        while(li < ri){
            mid = (li + ri) / 2;
            if(hull[mid].ti < t)
                li = mid + 1;
            else
                ri = mid;
        }
        return t * hull[li].ai + hull[li].bi;
    }
};

const int N = (int)1e6 + 10;
ll dp[N];
ll f[N];
ll a[N];

int main(){
    fastIO;
    int n;
    cin >> n;
    for(int i = 1 ; i <= n; i ++ ){
        f[i] = n-i+1;
        cin >> a[i];
    }
    ll x;
    vector<O> mono;
    O cur;
    ll ca, cb;
    for(int i = 1; i <= n; i ++ ){
        x = a[i];
        cur = {x, {{-f[i],-dp[i-1], (ll)1e18}}, -(ll)1e18};
        while(!mono.empty() && mono.back().vv <= cur.vv){
            swap(mono.back().hull, cur.hull);
            for(auto x : mono.back().hull){
                ca = x.ai;
                cb = x.bi;
                cur.add_line({ca, cb, (ll)1e18});
            }
            mono.pop_back();
        }
        cur.pf = cur.getval(x);
        if(!mono.empty())
            cur.pf = max(cur.pf, mono.back().pf);
        mono.push_back(cur);
        dp[i] = -mono.back().pf;
    }
    cout << dp[n];
    return 0;
}

Compilation message

Discharging.cpp: In function 'int main()':
Discharging.cpp:74:21: warning: narrowing conversion of '- f[i]' from 'll' {aka 'long long int'} to 'ld' {aka 'long double'} [-Wnarrowing]
   74 |         cur = {x, {{-f[i],-dp[i-1], (ll)1e18}}, -(ll)1e18};
      |                     ^~~~~
Discharging.cpp:74:27: warning: narrowing conversion of '- dp[(i - 1)]' from 'll' {aka 'long long int'} to 'ld' {aka 'long double'} [-Wnarrowing]
   74 |         cur = {x, {{-f[i],-dp[i-1], (ll)1e18}}, -(ll)1e18};
      |                           ^~~~~~~~
Discharging.cpp:80:31: warning: narrowing conversion of 'ca' from 'll' {aka 'long long int'} to 'ld' {aka 'long double'} [-Wnarrowing]
   80 |                 cur.add_line({ca, cb, (ll)1e18});
      |                               ^~
Discharging.cpp:80:35: warning: narrowing conversion of 'cb' from 'll' {aka 'long long int'} to 'ld' {aka 'long double'} [-Wnarrowing]
   80 |                 cur.add_line({ca, cb, (ll)1e18});
      |                                   ^~

Subtask #1
9.0 / 9.0

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

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 416 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 3 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 416 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 3 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Execution timed out 1031 ms 28920 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1144 ms 719220 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
14.0 / 14.0

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

Subtask #6
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 308 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 2 ms 416 KB Output is correct
21 Correct 2 ms 384 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 2 ms 384 KB Output is correct
24 Correct 2 ms 384 KB Output is correct
25 Correct 1 ms 384 KB Output is correct
26 Correct 2 ms 384 KB Output is correct
27 Correct 3 ms 384 KB Output is correct
28 Correct 2 ms 384 KB Output is correct
29 Correct 2 ms 384 KB Output is correct
30 Execution timed out 1031 ms 28920 KB Time limit exceeded
31 Halted 0 ms 0 KB -