Submission #596181

#	Time	Username	Problem	Language	Result	Execution time	Memory
596181		Mounir	Holding (COCI20_holding)	C++14	55 / 110	1212 ms	67788 KiB

holding

#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define sz(x) (int)x.size()
#define pb push_back
#define pii pair<int, int>
#define chmin(x, v) x = min(x, v)
#define chmax(x, v) x = max(x, v)
#define print(x) cout << #x << " est " << x << endl;
#define x first
#define y second
//#define int long long
using namespace std;

const int N = 205, OO = 1e9;
int gainMin[2][N][N * N];

signed main(){  
      int nVals, L, R, depMax; cin >> nVals >> L >> R >> depMax;
      --L; --R;
      vector<int> vals(nVals);
      for (int& val : vals)
            cin >> val;
      
      int INITIAL = 0;
      for (int i = L; i <= R; ++i)
            INITIAL += vals[i];

      for (int i = 0; i < N; ++i)
            for (int j = 0; j < N * N; ++j)
                  gainMin[0][i][j] = OO;
      
      int DELTA = (N * N)/2;
      gainMin[0][nVals][DELTA] = 0;
      for (int iMove = 0; iMove < nVals; ++iMove){
            for (int i = 0; i < N; ++i)
                  for (int j = 0; j < N * N; ++j)
                        gainMin[(iMove + 1)%2][i][j] = OO;
            for (int nDehors = 0; nDehors <  N; ++nDehors)
                  for (int sumDep = 0; sumDep < N * N; ++sumDep)
                        chmin(gainMin[(iMove + 1)%2][nDehors][sumDep], gainMin[iMove%2][nDehors][sumDep]);
            if (iMove < L){
                  //option 2 : prendre la valeur actuelle
                  for (int nDehors = 0; nDehors < N; ++nDehors)
                        for (int sumDep = 0; sumDep < N * N; ++sumDep){
                              int futDehors = nDehors + 1, futSum = sumDep - iMove;
                              if (!(futDehors < 0 || futDehors >= N || futSum < 0 || futSum >= N* N))
                                    chmin(gainMin[(iMove + 1)%2][futDehors][futSum], gainMin[iMove%2][nDehors][sumDep] + vals[iMove]);
                        }
            }
            else if (iMove <= R){
                  //option 2 : prendre la valeur actuelle
                  for (int nDehors = 1; nDehors < N; ++nDehors)
                        for (int sumDep = 0; sumDep < N * N; ++sumDep){
                              int futDehors = nDehors - 1, futSum = sumDep - iMove;
                        /* intile quand R = N     if (!(futDehors < 0 || futDehors >= N || futSum < 0 || futSum >= N* N))
                                    chmin(gainMin[(iMove + 1)%2][futDehors][futSum], gainMin[iMove%2][nDehors][sumDep] - vals[iMove]);
                        */      futSum = sumDep + iMove;
                              if (!(futDehors < 0 || futDehors >= N || futSum < 0 || futSum >= N* N))
                                    chmin(gainMin[(iMove + 1)%2][futDehors][futSum], gainMin[iMove%2][nDehors][sumDep] - vals[iMove]);
                        }
            }
            else {
                  //option 2 : prendre la valeur actuelle
                  for (int nDehors = 0; nDehors < N; ++nDehors)
                        for (int sumDep = 0; sumDep < N * N; ++sumDep){
                              int futDehors = nDehors + 1, futSum = sumDep + iMove;
                              if (!(futDehors < 0 || futDehors >= N || futSum < 0 || futSum >= N* N))
                                    chmin(gainMin[(iMove + 1)%2][futDehors][futSum], gainMin[iMove%2][nDehors][sumDep] + vals[iMove]);
                        }
            }
      }

      //(nVals%2, futDehors = nVals, futSum -= DELTA;
      int mini = OO;
      for (int futSum = DELTA; futSum <= DELTA + depMax; ++futSum)
            chmin(mini, gainMin[nVals%2][nVals][futSum]);
      cout << INITIAL + mini << endl;
      return 0;   
}

• Subtask 1: 22 / 22
• Subtask 2: 33 / 33
• Subtask 3: 0 / 33
• Subtask 4: 0 / 22