oj.uz

Submission #870767

# Submission time Handle Problem Language Result Execution time Memory
870767 2023-11-09T03:42:05 Z amogususus Holding (COCI20_holding) C++17
110 / 110
 19 ms 3484 KB 
#pragma GCC optimize("O2,unroll-loops,inline")
#pragma GCC target("avx2,bmi,bmi2")
#include<bits/stdc++.h>
#define ll int
#define ld long double
#define pb push_back
#define prec fixed<<setprecision
#define endl '\n'
#define all(x) x.begin(),x.end()
#define pll pair<ll,ll>
#define open(name) if(fopen(name".inp", "r")){freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
using namespace std;
const int maxN=103;
const int mod=998244353;
ll n,l,r,z,a[maxN],f[102][2503],old[102][2503],g[102][2503];
void Enter(){
    cin>>n>>l>>r>>z;
    z=min(z,n*n/4);
    ll res=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(l<=i&&i<=r)res+=a[i];
    }
    //f[i][j][k]=so tien giam bot lon nhat khi thay [L,j] bang cac ptu trong [1,i] voi chi phi k, swap(a[i],a[j])
    // tuong tu voi g
    for(int i=1;i<l;i++){
        for(int j=l;j<=r;j++)for(int k=0;k<=z;k++){
            f[j][k]=max(f[j-1][k],old[j][k]);
            if(k>=j-i)f[j][k]=max(f[j][k],old[j-1][k-j+i]+a[j]-a[i]);
        }
        swap(old,f);
    }
    swap(old,f);
    memset(old,0,sizeof old);
    for(int i=n;i>r;i--){
        for(int j=r;j>=l;j--)for(int k=0;k<=z;k++){
            g[j][k]=max(g[j+1][k],old[j][k]);
            if(k>=i-j)g[j][k]=max(g[j][k],old[j+1][k+j-i]+a[j]-a[i]);
        }
        swap(old,g);
    }
    swap(old,g);
    ll x=max(f[r][z],g[l][z]);
    for(int i=l;i<=r;i++)for(int k=0;k<=z;k++)x=max(x,f[i][k]+g[i+1][z-k]);
    cout<<res-x;
}
//amogus
signed main(){
    open("DEBT");
    cin.tie(nullptr);ios_base::sync_with_stdio(NULL);
    //ll t=1;cin>>t;while(t--)
    Enter();
}

Compilation message

holding.cpp: In function 'int main()':
holding.cpp:11:54: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 | #define open(name) if(fopen(name".inp", "r")){freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
      |                                               ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
holding.cpp:49:5: note: in expansion of macro 'open'
   49 |     open("DEBT");
      |     ^~~~
holding.cpp:11:87: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 | #define open(name) if(fopen(name".inp", "r")){freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
      |                                                                                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
holding.cpp:49:5: note: in expansion of macro 'open'
   49 |     open("DEBT");
      |     ^~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3420 KB Output is correct
2 Correct 3 ms 3420 KB Output is correct
3 Correct 2 ms 3420 KB Output is correct
4 Correct 2 ms 3420 KB Output is correct
5 Correct 2 ms 3420 KB Output is correct
6 Correct 2 ms 3420 KB Output is correct
7 Correct 3 ms 3420 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3420 KB Output is correct
2 Correct 3 ms 3420 KB Output is correct
3 Correct 2 ms 3420 KB Output is correct
4 Correct 2 ms 3420 KB Output is correct
5 Correct 2 ms 3420 KB Output is correct
6 Correct 2 ms 3420 KB Output is correct
7 Correct 3 ms 3420 KB Output is correct
8 Correct 7 ms 3416 KB Output is correct
9 Correct 7 ms 3420 KB Output is correct
10 Correct 6 ms 3228 KB Output is correct
11 Correct 6 ms 3420 KB Output is correct
12 Correct 4 ms 3420 KB Output is correct
13 Correct 6 ms 3260 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3420 KB Output is correct
2 Correct 3 ms 3420 KB Output is correct
3 Correct 2 ms 3420 KB Output is correct
4 Correct 2 ms 3420 KB Output is correct
5 Correct 2 ms 3420 KB Output is correct
6 Correct 2 ms 3420 KB Output is correct
7 Correct 3 ms 3420 KB Output is correct
8 Correct 7 ms 3416 KB Output is correct
9 Correct 7 ms 3420 KB Output is correct
10 Correct 6 ms 3228 KB Output is correct
11 Correct 6 ms 3420 KB Output is correct
12 Correct 4 ms 3420 KB Output is correct
13 Correct 6 ms 3260 KB Output is correct
14 Correct 10 ms 3420 KB Output is correct
15 Correct 9 ms 3232 KB Output is correct
16 Correct 9 ms 3420 KB Output is correct
17 Correct 9 ms 3448 KB Output is correct
18 Correct 8 ms 3416 KB Output is correct
19 Correct 6 ms 3420 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3420 KB Output is correct
2 Correct 3 ms 3420 KB Output is correct
3 Correct 2 ms 3420 KB Output is correct
4 Correct 2 ms 3420 KB Output is correct
5 Correct 2 ms 3420 KB Output is correct
6 Correct 2 ms 3420 KB Output is correct
7 Correct 3 ms 3420 KB Output is correct
8 Correct 7 ms 3416 KB Output is correct
9 Correct 7 ms 3420 KB Output is correct
10 Correct 6 ms 3228 KB Output is correct
11 Correct 6 ms 3420 KB Output is correct
12 Correct 4 ms 3420 KB Output is correct
13 Correct 6 ms 3260 KB Output is correct
14 Correct 10 ms 3420 KB Output is correct
15 Correct 9 ms 3232 KB Output is correct
16 Correct 9 ms 3420 KB Output is correct
17 Correct 9 ms 3448 KB Output is correct
18 Correct 8 ms 3416 KB Output is correct
19 Correct 6 ms 3420 KB Output is correct
20 Correct 19 ms 3484 KB Output is correct
21 Correct 18 ms 3232 KB Output is correct
22 Correct 16 ms 3420 KB Output is correct
23 Correct 18 ms 3224 KB Output is correct
24 Correct 8 ms 3420 KB Output is correct
25 Correct 17 ms 3416 KB Output is correct