oj.uz

Submission #270393

# Submission time Handle Problem Language Result Execution time Memory
270393 2020-08-17T14:43:37 Z doowey Discharging (NOI20_discharging) C++14
13 / 100
 1000 ms 709560 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){
            if(mono.back().hull.size() < cur.hull.size()){
                reverse(mono.back().hull.begin(), mono.back().hull.end());
                for(auto x : mono.back().hull){
                    ca = x.ai;
                    cb = x.bi;
                    cur.add_line({ca, cb, (ll)1e18});
                }
            }
            else{
                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:81:35: warning: narrowing conversion of 'ca' from 'll' {aka 'long long int'} to 'ld' {aka 'long double'} [-Wnarrowing]
   81 |                     cur.add_line({ca, cb, (ll)1e18});
      |                                   ^~
Discharging.cpp:81:39: warning: narrowing conversion of 'cb' from 'll' {aka 'long long int'} to 'ld' {aka 'long double'} [-Wnarrowing]
   81 |                     cur.add_line({ca, cb, (ll)1e18});
      |                                       ^~
Discharging.cpp:89:35: warning: narrowing conversion of 'ca' from 'll' {aka 'long long int'} to 'ld' {aka 'long double'} [-Wnarrowing]
   89 |                     cur.add_line({ca, cb, (ll)1e18});
      |                                   ^~
Discharging.cpp:89:39: warning: narrowing conversion of 'cb' from 'll' {aka 'long long int'} to 'ld' {aka 'long double'} [-Wnarrowing]
   89 |                     cur.add_line({ca, cb, (ll)1e18});
      |                                       ^~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 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 0 ms 384 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Incorrect 0 ms 384 KB Output isn't correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 384 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 1 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 3 ms 384 KB Output is correct
13 Correct 2 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 1 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 384 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 1 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 3 ms 384 KB Output is correct
13 Correct 2 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 Correct 973 ms 23800 KB Output is correct
17 Execution timed out 1079 ms 29360 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

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

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 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 0 ms 384 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Incorrect 0 ms 384 KB Output isn't correct

Subtask #6
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 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 0 ms 384 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Incorrect 0 ms 384 KB Output isn't correct