Submission #285021

#	Time	Username	Problem	Language	Result	Execution time	Memory
285021		mosiashvililuka	Discharging (NOI20_discharging)	C++14	0 / 100	219 ms	39800 KiB

Discharging

#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,f[1000009],mx,rg[1000009];
long long dp[1000009];
multiset <long long> s;
multiset <long long>::iterator it;
vector <long long> v[1000009];
stack <int> st;
int main(){
    //ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    scanf("%d",&a);
    scanf("\n");
    for(i=1; i<=a; i++) scanf("%d",&f[i]);
    mx=0;
    for(i=1; i<=a; i++){
        if(mx<f[i]) mx=f[i];
        dp[i]=mx*a;
        while(st.size()>0&&f[st.top()+1]<=f[i]){
            //zx=dp[st.top()]+(f[i]-f[st.top()+1])*(a-st.top());
            zx=dp[st.top()]+f[i]*(a-st.top());
            if(dp[i]>zx) dp[i]=zx;
            st.pop();
        }
        if(st.size()>0){
            zx=dp[st.top()]+f[st.top()+1]*(a-st.top());
            if(dp[i]>zx) dp[i]=zx;
        }
        if(dp[i]>dp[i-1]+f[i]*(a-i+1)) dp[i]=dp[i-1]+f[i]*(a-i+1);
        //cout<<dp[i]<<endl;
        st.push(i-1);
    }
    cout<<dp[a];
    return 0;
}

Compilation message (stderr)

Discharging.cpp: In function 'int main()':
Discharging.cpp:11:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   11 |     scanf("%d",&a);
      |     ~~~~~^~~~~~~~~
Discharging.cpp:12:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   12 |     scanf("\n");
      |     ~~~~~^~~~~~
Discharging.cpp:13:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   13 |     for(i=1; i<=a; i++) scanf("%d",&f[i]);
      |                         ~~~~~^~~~~~~~~~~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 13
• Subtask 3: 0 / 25
• Subtask 4: 0 / 11
• Subtask 5: 0 / 14
• Subtask 6: 0 / 28