oj.uz

Submission #696231

# Submission time Handle Problem Language Result Execution time Memory
696231 2023-02-06T02:53:24 Z aSSSd Holding (COCI20_holding) C++14
110 / 110
 158 ms 119288 KB 
#include<bits/stdc++.h>
using namespace std;
const int N=105;
int a[N],pref[N],dp[N][N][N*N/4];
int main()
{
    //freopen("ngu.inp","r",stdin);
    int n,l,r,k;
    cin >> n >> l >> r >> k;
    for(int i=1;i<=n;++i)
    {
        cin >> a[i];
        pref[i]=pref[i-1]+a[i];
    }
    k=min(k,n*n/4);
    memset(dp,50,sizeof dp);
    if(l!=1) dp[1][l][k]=pref[r]-pref[l-1];
    else dp[r+1][l][k]=pref[r]-pref[l-1];
    int ans=dp[0][0][0];
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=n;++j)
        {
            for(int p=0;p<=k;++p)
            {
                ans=min(ans,dp[i][j][p]);

                if(i>=l&&i<=r) continue;
                int nxti=i+1;
                if(nxti>=l&&nxti<=r) nxti=r+1;

                dp[nxti][j][p]=min(dp[nxti][j][p],dp[i][j][p]);
                dp[i][j+1][p]=min(dp[i][j+1][p],dp[i][j][p]);

                if(j<=r&&j>=l) if(i<l||i>r) if(p>=abs(j-i))
                    dp[nxti][j+1][p-abs(j-i)]=min(dp[nxti][j+1][p-abs(j-i)],dp[i][j][p]+a[i]-a[j]);

            }
        }
    }

    for(int i=1;i<=n+1;++i)
        for(int j=1;j<=n+1;++j)
            for(int p=0;p<=k;++p)
                ans=min(ans,dp[i][j][p]);
    cout << ans;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 119140 KB Output is correct
2 Correct 43 ms 119128 KB Output is correct
3 Correct 48 ms 119196 KB Output is correct
4 Correct 42 ms 119164 KB Output is correct
5 Correct 42 ms 119100 KB Output is correct
6 Correct 41 ms 119120 KB Output is correct
7 Correct 44 ms 119108 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 119140 KB Output is correct
2 Correct 43 ms 119128 KB Output is correct
3 Correct 48 ms 119196 KB Output is correct
4 Correct 42 ms 119164 KB Output is correct
5 Correct 42 ms 119100 KB Output is correct
6 Correct 41 ms 119120 KB Output is correct
7 Correct 44 ms 119108 KB Output is correct
8 Correct 44 ms 119224 KB Output is correct
9 Correct 46 ms 119288 KB Output is correct
10 Correct 49 ms 119176 KB Output is correct
11 Correct 46 ms 119116 KB Output is correct
12 Correct 45 ms 119116 KB Output is correct
13 Correct 51 ms 119200 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 119140 KB Output is correct
2 Correct 43 ms 119128 KB Output is correct
3 Correct 48 ms 119196 KB Output is correct
4 Correct 42 ms 119164 KB Output is correct
5 Correct 42 ms 119100 KB Output is correct
6 Correct 41 ms 119120 KB Output is correct
7 Correct 44 ms 119108 KB Output is correct
8 Correct 44 ms 119224 KB Output is correct
9 Correct 46 ms 119288 KB Output is correct
10 Correct 49 ms 119176 KB Output is correct
11 Correct 46 ms 119116 KB Output is correct
12 Correct 45 ms 119116 KB Output is correct
13 Correct 51 ms 119200 KB Output is correct
14 Correct 43 ms 119116 KB Output is correct
15 Correct 44 ms 119116 KB Output is correct
16 Correct 48 ms 119140 KB Output is correct
17 Correct 50 ms 119172 KB Output is correct
18 Correct 46 ms 119148 KB Output is correct
19 Correct 51 ms 119104 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 119140 KB Output is correct
2 Correct 43 ms 119128 KB Output is correct
3 Correct 48 ms 119196 KB Output is correct
4 Correct 42 ms 119164 KB Output is correct
5 Correct 42 ms 119100 KB Output is correct
6 Correct 41 ms 119120 KB Output is correct
7 Correct 44 ms 119108 KB Output is correct
8 Correct 44 ms 119224 KB Output is correct
9 Correct 46 ms 119288 KB Output is correct
10 Correct 49 ms 119176 KB Output is correct
11 Correct 46 ms 119116 KB Output is correct
12 Correct 45 ms 119116 KB Output is correct
13 Correct 51 ms 119200 KB Output is correct
14 Correct 43 ms 119116 KB Output is correct
15 Correct 44 ms 119116 KB Output is correct
16 Correct 48 ms 119140 KB Output is correct
17 Correct 50 ms 119172 KB Output is correct
18 Correct 46 ms 119148 KB Output is correct
19 Correct 51 ms 119104 KB Output is correct
20 Correct 65 ms 119204 KB Output is correct
21 Correct 79 ms 119200 KB Output is correct
22 Correct 48 ms 119204 KB Output is correct
23 Correct 149 ms 119200 KB Output is correct
24 Correct 58 ms 119116 KB Output is correct
25 Correct 158 ms 119200 KB Output is correct