oj.uz

Submission #596207

# Submission time Handle Problem Language Result Execution time Memory
596207 2022-07-14T13:21:57 Z Mounir Holding (COCI20_holding) C++14
0 / 110
 626 ms 135156 KB 
#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][2];
 
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][0] = gainMin[0][i][j][1] = OO;
      
      int DELTA = (N * N)/2;
      gainMin[0][nVals][DELTA][0] = 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][0] = gainMin[(iMove + 1)%2][i][j][1] = OO;
            for (int nDehors = 0; nDehors <  N; ++nDehors)
                  for (int sumDep = 0; sumDep < N * N; ++sumDep)
                        for (int j = 0; j < 2; ++j)   
                              chmin(gainMin[(iMove + 1)%2][nDehors][sumDep][j], gainMin[iMove%2][nDehors][sumDep][j]);
            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][0], gainMin[iMove%2][nDehors][sumDep][0] + 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;
                              if (!(futDehors < 0 || futDehors >= N || futSum < 0 || futSum >= N* N))
                                    chmin(gainMin[(iMove + 1)%2][futDehors][futSum][0], gainMin[iMove%2][nDehors][sumDep][0] - vals[iMove]);
                              futSum = sumDep - iMove;
                              if (!(futDehors < 0 || futDehors >= N || futSum < 0 || futSum >= N* N))
                                    chmin(gainMin[(iMove + 1)%2][futDehors][futSum][1], min(gainMin[iMove%2][nDehors][sumDep][0], gainMin[iMove%2][nDehors][sumDep][1]) - vals[iMove]);
                        }
            }
            else {
                  //option 2 : prendre la valeur actuelle
                  for (int nDehors = 0; nDehors < N; ++nDehors)
                        for (int sumDep = 0; sumDep < N * N; ++sumDep){
                              for (int j = 0; j < 2; ++j){
                                    int futDehors = nDehors + 1, futSum = sumDep + iMove;
                                    if (!(futDehors < 0 || futDehors >= N || futSum < 0 || futSum >= N* N))
                                          chmin(gainMin[(iMove + 1)%2][futDehors][futSum][j], gainMin[iMove%2][nDehors][sumDep][j] + vals[iMove]);
                              }
                        }
            }

            if (iMove == 1 && false)
                  cout << "req " << gainMin[(iMove+1)%2][nVals - 1][DELTA - 1][1] << endl;
      }
 
      //(nVals%2, futDehors = nVals, futSum -= DELTA;
      int mini = OO;
      for (int futSum = DELTA; futSum <= DELTA + depMax; ++futSum)
            for (int j = 0; j < 2; ++j)   
                  chmin(mini, gainMin[nVals%2][nVals][futSum][j]);
      cout << INITIAL + mini << endl;
      return 0;   
}

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 135156 KB Output is correct
2 Incorrect 626 ms 135156 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 135156 KB Output is correct
2 Incorrect 626 ms 135156 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 135156 KB Output is correct
2 Incorrect 626 ms 135156 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 135156 KB Output is correct
2 Incorrect 626 ms 135156 KB Output isn't correct
3 Halted 0 ms 0 KB -