oj.uz

Submission #486882

# Submission time Handle Problem Language Result Execution time Memory
486882 2021-11-13T07:17:59 Z kakayoshi Holding (COCI20_holding) C++14
22 / 110
 139 ms 262148 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pi;
typedef pair<ll, pair<ll, ll> > pii;
typedef vector <ll> vi;
#define forw(i,a,b) for (ll i=a;i<=(b);i++)
#define forb(i,a,b) for (ll i=a;i>=(b);i--)
#define fast {ios::sync_with_stdio(false); cin.tie(0); }
#define fi first
#define se second
#define pu push
#define puf push_front
#define pb push_back
#define pof pop_front
#define pob pop_back
#define fr front
#define all(a) a.begin(),a.end()
const ll oo=1e18;
const ll mod=(1<<31)-1;
const int base=31;
const int tx[5]={0,-1,0,1,0};
const int ty[5]={0,0,1,0,-1};
const ll maxN=5e5+5;
const ll maxM=2e5+5;
const ll block=700;
int n,l,r,k,sum,a[105],ans,pre[105][10005],suf[105][10005];
vector <int> dp1[105][10005],dp2[105][10005];
void minimize(int &a,int b)
{
    a=min(a,b);
}
void solve()
{
    cin>>n>>l>>r>>k;
    int num=r-l+1;
    forw(i,0,n+2)
        forw(cost,0,k+2)
        {
            dp1[i][cost].assign(n+5,0);
            dp2[i][cost].assign(n+5,0);
        }
    forw(i,1,n)
    {
        cin>>a[i];
        if (l<=i && i<=r)
        sum+=a[i];
    }
    forw(i,0,n+1)
        forw(cost,0,k)
            forw(j,0,n)
                dp1[i][cost][j]=dp2[i][cost][j]=1e9;
    dp1[0][0][0]=dp2[n+1][0][0]=sum;
    ////////////////////////////////////// left to right
    forw(i,0,l-2)
    {
        forw(cost,0,k)
        {
            int res=1e9;
            forw(j,0,num)
            {
                res=min(res,dp1[i][cost][j]);
                minimize(dp1[i+1][cost][j],res);
                if (j<num && cost+ (l+j) - (i+1) <=k)
                    minimize(dp1[i+1][cost+ (l+j) - (i+1)][j+1],res-(a[l+j]-a[i+1]));
            }
        }
    }
    forw(j,0,num)
    {
        int res=1e9;
        forw(cost,0,k)
        {
            minimize(res,dp1[l-1][cost][j]);
            if (j>0) pre[j][cost]=min(res,pre[j-1][cost]);
            else pre[j][cost]=res;
        }
    }
    //////////////////////////////////////// right to left
    forb(i,n+1,r+2)
    {
        forw(cost,0,k)
        {
            int res=1e9;
            forw(j,0,num)
            {
                res=min(res,dp2[i][cost][j]);
                minimize(dp2[i-1][cost][j],res);
                if (j<num && cost + (i-1) - (r-j) <=k)
                    minimize(dp2[i-1][cost + (i-1) - (r-j)][j+1],res-(a[r-j]-a[i-1]));
            }
        }
    }
    forw(j,0,num)
    {
        int res=1e9;
        forw(cost,0,k)
        {
            minimize(res,dp2[r+1][cost][j]);
            if (j>0) suf[j][cost]=min(res,suf[j-1][cost]);
            else suf[j][cost]=res;
        }
    }
    ans=sum;
    forw(j,0,num)
    {
        forw(cost,0,k)
        {
            //cout<<j<<" "<<cost<<" "<<pre[j][cost]<<" "<<suf[num-j][k-cost]<<endl;
            minimize(ans,pre[j][cost]+suf[num-j][k-cost]-sum);
        }
    }
    cout<<ans;
}
int main()
{
    fast;
   // freopen("test.inp","r",stdin);
   // freopen("test.out","w",stdout);
    solve();
    return 0;
}

Compilation message

holding.cpp:21:21: warning: integer overflow in expression of type 'int' results in '2147483647' [-Woverflow]
   21 | const ll mod=(1<<31)-1;
      |              ~~~~~~~^~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 49612 KB Output is correct
2 Correct 23 ms 49708 KB Output is correct
3 Correct 22 ms 49724 KB Output is correct
4 Correct 22 ms 49828 KB Output is correct
5 Correct 23 ms 49756 KB Output is correct
6 Correct 24 ms 49892 KB Output is correct
7 Correct 49 ms 73880 KB Output is correct

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 49612 KB Output is correct
2 Correct 23 ms 49708 KB Output is correct
3 Correct 22 ms 49724 KB Output is correct
4 Correct 22 ms 49828 KB Output is correct
5 Correct 23 ms 49756 KB Output is correct
6 Correct 24 ms 49892 KB Output is correct
7 Correct 49 ms 73880 KB Output is correct
8 Correct 23 ms 51020 KB Output is correct
9 Correct 24 ms 51788 KB Output is correct
10 Correct 24 ms 52096 KB Output is correct
11 Correct 27 ms 54732 KB Output is correct
12 Correct 24 ms 52392 KB Output is correct
13 Runtime error 139 ms 262148 KB Execution killed with signal 9

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 49612 KB Output is correct
2 Correct 23 ms 49708 KB Output is correct
3 Correct 22 ms 49724 KB Output is correct
4 Correct 22 ms 49828 KB Output is correct
5 Correct 23 ms 49756 KB Output is correct
6 Correct 24 ms 49892 KB Output is correct
7 Correct 49 ms 73880 KB Output is correct
8 Correct 23 ms 51020 KB Output is correct
9 Correct 24 ms 51788 KB Output is correct
10 Correct 24 ms 52096 KB Output is correct
11 Correct 27 ms 54732 KB Output is correct
12 Correct 24 ms 52392 KB Output is correct
13 Runtime error 139 ms 262148 KB Execution killed with signal 9

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 49612 KB Output is correct
2 Correct 23 ms 49708 KB Output is correct
3 Correct 22 ms 49724 KB Output is correct
4 Correct 22 ms 49828 KB Output is correct
5 Correct 23 ms 49756 KB Output is correct
6 Correct 24 ms 49892 KB Output is correct
7 Correct 49 ms 73880 KB Output is correct
8 Correct 23 ms 51020 KB Output is correct
9 Correct 24 ms 51788 KB Output is correct
10 Correct 24 ms 52096 KB Output is correct
11 Correct 27 ms 54732 KB Output is correct
12 Correct 24 ms 52392 KB Output is correct
13 Runtime error 139 ms 262148 KB Execution killed with signal 9