oj.uz

Submission #853308

# Submission time Handle Problem Language Result Execution time Memory
853308 2023-09-24T03:44:46 Z 8pete8 Discharging (NOI20_discharging) C++17
0 / 100
 102 ms 23900 KB 
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
#define int long long
const int mxn=1e5,mod=1000000007,lg=20,root=1000,inf=1e18;
struct line{int m,c;};
double intersect(line a,line b){return ((b.c-a.c)*1.0/(a.m-b.m)*1.0);}
static bool cmp(pair<int,line>a,pair<int,line>b){return a.f<b.f;}
vector<pair<int,line>>con;
void add(line a){
    while(con.size()>1&&(intersect(con.back().s,a)<=(intersect(con[con.size()-1].s,con[con.size()-2].s))))con.pop_back();
    if(con.empty())con.pb({0,a});
    else con.pb({intersect(con.back().s,a),a});
}
int qry(int x){
    auto it=ub(all(con),make_pair(x,line{}),cmp);
    it--;
    line tmp=(*it).s;
    return x*(tmp.m)+tmp.c;
}
/*
dpi =dp(j)+ti*(n-j+1)
*/
int32_t main(){
    fastio
    int n;cin>>n;
    vector<int>v(n+1),p(n+1),dp(n+1,INT_MAX);
    dp[0]=0;
    for(int i=1;i<=n;i++)cin>>v[i];
    for(int i=1;i<=n;i++)p[i]=max(p[i-1],v[i]),v[i]=p[i];
    add(line{0,0});
    for(int i=1;i<=n;i++){
        if(v[i]==v[i-1]&&i>1)dp[i]=dp[i-1];
        //ti(1-j)+dp(j-1)
        //-tij+dp(j-1)+ti
        add(line{-i,dp[i-1]});
        dp[i]=min(dp[i],qry(v[i])+v[i]*(n+1));
    }
    cout<<dp[n]<<'\n';
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 102 ms 23900 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -