oj.uz

Submission #596168

# Submission time Handle Problem Language Result Execution time Memory
596168 2022-07-14T12:51:07 Z Mounir Holding (COCI20_holding) C++14
55 / 110
 1433 ms 67788 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];

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 = 0; futSum < N * N; ++futSum){
            if (futSum <= DELTA + depMax)
                  chmin(mini, gainMin[nVals%2][nVals][futSum]);
                  
      }
      cout << INITIAL + mini << endl;
      return 0;   
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 67716 KB Output is correct
2 Correct 339 ms 67788 KB Output is correct
3 Correct 336 ms 67720 KB Output is correct
4 Correct 347 ms 67720 KB Output is correct
5 Correct 336 ms 67716 KB Output is correct
6 Correct 367 ms 67724 KB Output is correct
7 Correct 328 ms 67660 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 67716 KB Output is correct
2 Correct 339 ms 67788 KB Output is correct
3 Correct 336 ms 67720 KB Output is correct
4 Correct 347 ms 67720 KB Output is correct
5 Correct 336 ms 67716 KB Output is correct
6 Correct 367 ms 67724 KB Output is correct
7 Correct 328 ms 67660 KB Output is correct
8 Correct 1217 ms 67720 KB Output is correct
9 Correct 1249 ms 67720 KB Output is correct
10 Correct 1261 ms 67720 KB Output is correct
11 Correct 1352 ms 67724 KB Output is correct
12 Correct 1294 ms 67720 KB Output is correct
13 Correct 1318 ms 67720 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 67716 KB Output is correct
2 Correct 339 ms 67788 KB Output is correct
3 Correct 336 ms 67720 KB Output is correct
4 Correct 347 ms 67720 KB Output is correct
5 Correct 336 ms 67716 KB Output is correct
6 Correct 367 ms 67724 KB Output is correct
7 Correct 328 ms 67660 KB Output is correct
8 Correct 1217 ms 67720 KB Output is correct
9 Correct 1249 ms 67720 KB Output is correct
10 Correct 1261 ms 67720 KB Output is correct
11 Correct 1352 ms 67724 KB Output is correct
12 Correct 1294 ms 67720 KB Output is correct
13 Correct 1318 ms 67720 KB Output is correct
14 Correct 1433 ms 67720 KB Output is correct
15 Correct 1288 ms 67720 KB Output is correct
16 Incorrect 1351 ms 67716 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 67716 KB Output is correct
2 Correct 339 ms 67788 KB Output is correct
3 Correct 336 ms 67720 KB Output is correct
4 Correct 347 ms 67720 KB Output is correct
5 Correct 336 ms 67716 KB Output is correct
6 Correct 367 ms 67724 KB Output is correct
7 Correct 328 ms 67660 KB Output is correct
8 Correct 1217 ms 67720 KB Output is correct
9 Correct 1249 ms 67720 KB Output is correct
10 Correct 1261 ms 67720 KB Output is correct
11 Correct 1352 ms 67724 KB Output is correct
12 Correct 1294 ms 67720 KB Output is correct
13 Correct 1318 ms 67720 KB Output is correct
14 Correct 1433 ms 67720 KB Output is correct
15 Correct 1288 ms 67720 KB Output is correct
16 Incorrect 1351 ms 67716 KB Output isn't correct
17 Halted 0 ms 0 KB -