oj.uz

Submission #596181

# Submission time Handle Problem Language Result Execution time Memory
596181 2022-07-14T13:00:23 Z Mounir Holding (COCI20_holding) C++14
55 / 110
 1212 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 = DELTA; futSum <= DELTA + depMax; ++futSum)
            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 136 ms 67720 KB Output is correct
2 Correct 363 ms 67648 KB Output is correct
3 Correct 312 ms 67712 KB Output is correct
4 Correct 366 ms 67740 KB Output is correct
5 Correct 317 ms 67720 KB Output is correct
6 Correct 319 ms 67720 KB Output is correct
7 Correct 308 ms 67720 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 67720 KB Output is correct
2 Correct 363 ms 67648 KB Output is correct
3 Correct 312 ms 67712 KB Output is correct
4 Correct 366 ms 67740 KB Output is correct
5 Correct 317 ms 67720 KB Output is correct
6 Correct 319 ms 67720 KB Output is correct
7 Correct 308 ms 67720 KB Output is correct
8 Correct 1147 ms 67712 KB Output is correct
9 Correct 1141 ms 67712 KB Output is correct
10 Correct 1205 ms 67716 KB Output is correct
11 Correct 1164 ms 67716 KB Output is correct
12 Correct 1151 ms 67788 KB Output is correct
13 Correct 1163 ms 67716 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 67720 KB Output is correct
2 Correct 363 ms 67648 KB Output is correct
3 Correct 312 ms 67712 KB Output is correct
4 Correct 366 ms 67740 KB Output is correct
5 Correct 317 ms 67720 KB Output is correct
6 Correct 319 ms 67720 KB Output is correct
7 Correct 308 ms 67720 KB Output is correct
8 Correct 1147 ms 67712 KB Output is correct
9 Correct 1141 ms 67712 KB Output is correct
10 Correct 1205 ms 67716 KB Output is correct
11 Correct 1164 ms 67716 KB Output is correct
12 Correct 1151 ms 67788 KB Output is correct
13 Correct 1163 ms 67716 KB Output is correct
14 Correct 1212 ms 67712 KB Output is correct
15 Correct 1148 ms 67716 KB Output is correct
16 Incorrect 1155 ms 67712 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 67720 KB Output is correct
2 Correct 363 ms 67648 KB Output is correct
3 Correct 312 ms 67712 KB Output is correct
4 Correct 366 ms 67740 KB Output is correct
5 Correct 317 ms 67720 KB Output is correct
6 Correct 319 ms 67720 KB Output is correct
7 Correct 308 ms 67720 KB Output is correct
8 Correct 1147 ms 67712 KB Output is correct
9 Correct 1141 ms 67712 KB Output is correct
10 Correct 1205 ms 67716 KB Output is correct
11 Correct 1164 ms 67716 KB Output is correct
12 Correct 1151 ms 67788 KB Output is correct
13 Correct 1163 ms 67716 KB Output is correct
14 Correct 1212 ms 67712 KB Output is correct
15 Correct 1148 ms 67716 KB Output is correct
16 Incorrect 1155 ms 67712 KB Output isn't correct
17 Halted 0 ms 0 KB -