oj.uz

Submission #285055

# Submission time Handle Problem Language Result Execution time Memory
285055 2020-08-28T09:34:52 Z mosiashvililuka Discharging (NOI20_discharging) C++14
20 / 100
 839 ms 34288 KB 
#include<bits/stdc++.h>
using namespace std;
long long f[1000009],mx,rg[1000009],mn[1000009];
long long dp[1000009],a,b,c,d,e,i,j,ii,jj,zx,xc;
stack <long long> st;
int main(){
    //ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    scanf("%I64d",&a);
    scanf("\n");
    for(i=1; i<=a; i++) scanf("%I64d",&f[i]);
    mx=0;
    st.push(0);
    mn[1]=f[1]*a;
    for(i=1; i<=a; i++){
        if(mx<f[i]) mx=f[i];
        dp[i]=mx*a;
        xc=999999999999999999LL;
        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(xc>mn[st.size()]) xc=mn[st.size()];
            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(xc>mn[st.size()]) xc=mn[st.size()];
            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);
        st.push(i-1);
        mn[st.size()]=dp[i-1]+f[i]*(a-i+1);
        if(mn[st.size()]>xc) mn[st.size()]=xc;
        //cout<<dp[i]<<endl;
    }
    cout<<dp[a];
    return 0;
}

Compilation message

Discharging.cpp: In function 'int main()':
Discharging.cpp:8:16: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
    8 |     scanf("%I64d",&a);
      |            ~~~~^  ~~
      |                |  |
      |                |  long long int*
      |                int*
      |            %I64lld
Discharging.cpp:10:36: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   10 |     for(i=1; i<=a; i++) scanf("%I64d",&f[i]);
      |                                ~~~~^  ~~~~~
      |                                    |  |
      |                                    |  long long int*
      |                                    int*
      |                                %I64lld
Discharging.cpp:8:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    8 |     scanf("%I64d",&a);
      |     ~~~~~^~~~~~~~~~~~
Discharging.cpp:9:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    9 |     scanf("\n");
      |     ~~~~~^~~~~~
Discharging.cpp:10:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   10 |     for(i=1; i<=a; i++) scanf("%I64d",&f[i]);
      |                         ~~~~~^~~~~~~~~~~~~~~

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 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 416 KB Output is correct
8 Correct 1 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 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct

Subtask #2
0 / 13.0

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

Subtask #3
0 / 25.0

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

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 839 ms 33384 KB Output is correct
2 Correct 810 ms 34288 KB Output is correct
3 Correct 828 ms 34248 KB Output is correct
4 Correct 807 ms 33336 KB Output is correct
5 Correct 836 ms 33136 KB Output is correct
6 Correct 825 ms 33120 KB Output is correct
7 Correct 807 ms 33384 KB Output is correct
8 Correct 809 ms 33288 KB Output is correct
9 Correct 817 ms 33220 KB Output is correct
10 Correct 804 ms 33160 KB Output is correct

Subtask #5
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 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 416 KB Output is correct
8 Correct 1 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 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Incorrect 2 ms 384 KB Output isn't correct
16 Halted 0 ms 0 KB -

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 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 416 KB Output is correct
8 Correct 1 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 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Incorrect 2 ms 384 KB Output isn't correct
16 Halted 0 ms 0 KB -