oj.uz

Submission #696230

# Submission time Handle Problem Language Result Execution time Memory
696230 2023-02-06T02:46:51 Z aSSSd Holding (COCI20_holding) C++14
110 / 110
 91 ms 100840 KB 
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r)
{
    return l+rng()%(r-l+1);
}
#define fasty ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define forinc(x,a,b) for(int x=a;x<=b;x++)
#define fordec(x,a,b) for(int x=a;x>=b;x--)
#define iii pair<ii,int>
#define fi first
#define se second
#define ii pair<int,int>
#define getbit(x,i) ((x>>(i))&1ll)
#define batbit(x,i) (x|(1ll<<(i)))
#define tatbit(x,i) (x&~(1ll<<(i)))
#define endl '\n'
//#define int long long
#define pb push_back
#define ll long long
const int N = 103;
const int K = 1e4+3;
int n,L,R,k;
int a[N];
int f[N][N][2510];
main()
{
    fasty;
    cin >> n >> L >> R >> k;
    vector<ii> c;
    vector<ii> d;
    k=min(k , n*n / 4);
    int sum=0;
    forinc(i,1,n)
    {
        cin >> a[i];
        if(i<L || i > R) c.pb({a[i] , i});
        else
        {
            d.pb({a[i] ,i});
            sum+=a[i];
        }
    }
    forinc(i,0,n) forinc(j,0,n) forinc(t,0,k) f[i][j][t]=sum;
    int n1 = c.size();
    int n2 = d.size();
    int res=sum;
    forinc(i,1,n1) forinc(j,1,n2) forinc(t,0,k)
    {
        int cost = abs(c[i-1].se - d[j-1].se);
        f[i][j][t] = min(f[i-1][j][t] , f[i][j-1][t]);
        if(t) f[i][j][t] = min(f[i][j][t] , f[i][j][t-1]);
        if(t>=cost)
        {
            f[i][j][t] = min(f[i-1][j-1][t-cost] - d[j-1].fi + c[i-1].fi , f[i][j][t]);
        }
    }
    forinc(i,1,n1) forinc(j,1,n2) forinc(t,0,k)
    {
        res = min(res , f[i][j][t]);
    }
    cout << res;
}

Compilation message

holding.cpp:27:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   27 | main()
      | ^~~~

Subtask #1
22.0 / 22.0

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

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Correct 1 ms 1108 KB Output is correct
4 Correct 1 ms 1108 KB Output is correct
5 Correct 1 ms 1108 KB Output is correct
6 Correct 1 ms 1108 KB Output is correct
7 Correct 1 ms 980 KB Output is correct
8 Correct 5 ms 11348 KB Output is correct
9 Correct 5 ms 11604 KB Output is correct
10 Correct 5 ms 11732 KB Output is correct
11 Correct 6 ms 12756 KB Output is correct
12 Correct 6 ms 11732 KB Output is correct
13 Correct 10 ms 17172 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Correct 1 ms 1108 KB Output is correct
4 Correct 1 ms 1108 KB Output is correct
5 Correct 1 ms 1108 KB Output is correct
6 Correct 1 ms 1108 KB Output is correct
7 Correct 1 ms 980 KB Output is correct
8 Correct 5 ms 11348 KB Output is correct
9 Correct 5 ms 11604 KB Output is correct
10 Correct 5 ms 11732 KB Output is correct
11 Correct 6 ms 12756 KB Output is correct
12 Correct 6 ms 11732 KB Output is correct
13 Correct 10 ms 17172 KB Output is correct
14 Correct 4 ms 10836 KB Output is correct
15 Correct 4 ms 11604 KB Output is correct
16 Correct 5 ms 11220 KB Output is correct
17 Correct 5 ms 12372 KB Output is correct
18 Correct 7 ms 13268 KB Output is correct
19 Correct 11 ms 17188 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Correct 1 ms 1108 KB Output is correct
4 Correct 1 ms 1108 KB Output is correct
5 Correct 1 ms 1108 KB Output is correct
6 Correct 1 ms 1108 KB Output is correct
7 Correct 1 ms 980 KB Output is correct
8 Correct 5 ms 11348 KB Output is correct
9 Correct 5 ms 11604 KB Output is correct
10 Correct 5 ms 11732 KB Output is correct
11 Correct 6 ms 12756 KB Output is correct
12 Correct 6 ms 11732 KB Output is correct
13 Correct 10 ms 17172 KB Output is correct
14 Correct 4 ms 10836 KB Output is correct
15 Correct 4 ms 11604 KB Output is correct
16 Correct 5 ms 11220 KB Output is correct
17 Correct 5 ms 12372 KB Output is correct
18 Correct 7 ms 13268 KB Output is correct
19 Correct 11 ms 17188 KB Output is correct
20 Correct 25 ms 57172 KB Output is correct
21 Correct 29 ms 67024 KB Output is correct
22 Correct 15 ms 42580 KB Output is correct
23 Correct 48 ms 100840 KB Output is correct
24 Correct 24 ms 53444 KB Output is correct
25 Correct 91 ms 100804 KB Output is correct