oj.uz

Submission #486883

# Submission time Handle Problem Language Result Execution time Memory
486883 2021-11-13T07:19:19 Z kakayoshi Holding (COCI20_holding) C++14
22 / 110
 149 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+5)
        forw(cost,0,k+5)
        {
            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 21 ms 49612 KB Output is correct
2 Correct 22 ms 49720 KB Output is correct
3 Correct 23 ms 49740 KB Output is correct
4 Correct 25 ms 49848 KB Output is correct
5 Correct 29 ms 49740 KB Output is correct
6 Correct 23 ms 49896 KB Output is correct
7 Correct 66 ms 78460 KB Output is correct

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 49612 KB Output is correct
2 Correct 22 ms 49720 KB Output is correct
3 Correct 23 ms 49740 KB Output is correct
4 Correct 25 ms 49848 KB Output is correct
5 Correct 29 ms 49740 KB Output is correct
6 Correct 23 ms 49896 KB Output is correct
7 Correct 66 ms 78460 KB Output is correct
8 Correct 23 ms 51204 KB Output is correct
9 Correct 23 ms 52080 KB Output is correct
10 Correct 28 ms 52216 KB Output is correct
11 Correct 27 ms 55060 KB Output is correct
12 Correct 28 ms 52564 KB Output is correct
13 Runtime error 149 ms 262148 KB Execution killed with signal 9

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 49612 KB Output is correct
2 Correct 22 ms 49720 KB Output is correct
3 Correct 23 ms 49740 KB Output is correct
4 Correct 25 ms 49848 KB Output is correct
5 Correct 29 ms 49740 KB Output is correct
6 Correct 23 ms 49896 KB Output is correct
7 Correct 66 ms 78460 KB Output is correct
8 Correct 23 ms 51204 KB Output is correct
9 Correct 23 ms 52080 KB Output is correct
10 Correct 28 ms 52216 KB Output is correct
11 Correct 27 ms 55060 KB Output is correct
12 Correct 28 ms 52564 KB Output is correct
13 Runtime error 149 ms 262148 KB Execution killed with signal 9

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 49612 KB Output is correct
2 Correct 22 ms 49720 KB Output is correct
3 Correct 23 ms 49740 KB Output is correct
4 Correct 25 ms 49848 KB Output is correct
5 Correct 29 ms 49740 KB Output is correct
6 Correct 23 ms 49896 KB Output is correct
7 Correct 66 ms 78460 KB Output is correct
8 Correct 23 ms 51204 KB Output is correct
9 Correct 23 ms 52080 KB Output is correct
10 Correct 28 ms 52216 KB Output is correct
11 Correct 27 ms 55060 KB Output is correct
12 Correct 28 ms 52564 KB Output is correct
13 Runtime error 149 ms 262148 KB Execution killed with signal 9