oj.uz

Submission #738137

# Submission time Handle Problem Language Result Execution time Memory
738137 2023-05-08T08:04:54 Z Sam_a17 Holding (COCI20_holding) C++17
110 / 110
 272 ms 199924 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//#include "temp.cpp"
#include <cstdio>
using namespace std;
 
#ifndef ONLINE_JUDGE
#define dbg(x) cerr << #x <<" "; print(x); cerr << endl;
#else
#define dbg(x)
#endif
 
#define sz(x) (int((x).size()))
#define len(x) (int)x.length()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define clr(x) (x).clear()
#define uniq(x) x.resize(unique(all(x)) - x.begin());
#define blt(x) __builtin_popcount(x)
 
#define pb push_back
#define popf pop_front
#define popb pop_back
 
void print(long long t) {cerr << t;}
void print(int t) {cerr << t;}
void print(string t) {cerr << t;}
void print(char t) {cerr << t;}
void print(double t) {cerr << t;}
void print(long double t) {cerr << t;}
void print(unsigned long long t) {cerr << t;}
 
template <class T, class V> void print(pair <T, V> p);
template <class T> void print(vector <T> v);
template <class T> void print(set <T> v);
template <class T, class V> void print(map <T, V> v);
template <class T> void print(multiset <T> v);
template <class T, class V> void print(T v[],V n) {cerr << "["; for(int i = 0; i < n; i++) {print(v[i]); cerr << " "; } cerr << "]";}
template <class T, class V> void print(pair <T, V> p) {cerr << "{"; print(p.first); cerr << ","; print(p.second); cerr << "}";}
template <class T> void print(vector <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(deque <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(set <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(multiset <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void print(map <T, V> v) {cerr << "[ "; for (auto i : v) {print(i); cerr << " ";} cerr << "]";}
 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define nl '\n'
 
// for grid problems
int dx[8] = {-1,0,1,0,1,-1,1,-1};
int dy[8] = {0,1,0,-1,1,1,-1,-1};

int ka() {
	int x = 0;
	bool z = false;
	while (1)
	{
		char y = getchar();
		if (y == '-')
			z = true;
		else if ('0' <= y && y <= '9')
			x = x * 10 + y - '0';
		else
		{
			if (z)
				x *= -1;
			return x;
		}
	}
}

// lowest / (1 << 17) >= 1e5 / (1 << 18) >= 2e5 / (1 << 21) >= 1e6
void fastIO() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr); cout.tie(nullptr);
}
// file in/out
void setIO(string str = "") {
  fastIO();
 
  if (str != "") {
    freopen((str + ".in").c_str(), "r", stdin);
    freopen((str + ".out").c_str(), "w", stdout);
  }
}
// Indexed Set
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 101, M = (1e4 + 1) / 4, inf = 1e9;
int dpL[N][N][M];
int dpR[N][N][M];
int n, l, r, k;
int a[N];

int solveL(int li, int ri, int cur) {
  if(li == 0 || ri == l - 1) {
    return 0;
  }

  if(dpL[li][ri][cur] != inf) {
    return dpL[li][ri][cur];
  }

  int ans = min(solveL(li - 1, ri, cur), solveL(li, ri - 1, cur));

  if(cur - (ri - li) >= 0) {
    ans = min(ans, solveL(li - 1, ri - 1, cur - (ri - li)) + a[li] - a[ri]);
  }

  dpL[li][ri][cur] = ans;
  return ans;
}

int solveR(int li, int ri, int cur) {
  if(li == r + 1 || ri == n + 1) {
    return 0;
  }

  if(dpR[li][ri][cur] != inf) {
    return dpR[li][ri][cur];
  }

  int ans = min(solveR(li + 1, ri, cur), solveR(li, ri + 1, cur));

  if(cur >= (ri - li)) {
    ans = min(ans, solveR(li + 1, ri + 1, cur - (ri - li)) + a[ri] - a[li]);
  }

  dpR[li][ri][cur] = ans;
  return ans;
}


void solve_() {
  cin >> n >> l >> r >> k;
  k = min(k, M);
  
  for(int i = 1; i <= n; i++) {
    cin >> a[i];
  }

  int s = 0;
  for(int i = l; i <= r; i++) {
    s += a[i];
  }
;
  for(int i = 0; i < N; i++) {
    for(int j = 0; j < N; j++) {
      for(int e = 0; e < M; e++) {
        dpL[i][j][e] = inf;
        dpR[i][j][e] = inf;
      }
    }
  }

  int ans = s, mn = inf;
  for(int i = 0; i <= k; i++) {
    mn = min(mn, solveL(l - 1, r, i));
    mn = min(mn, solveR(l, r + 1, i));
  }

  for(int i = l; i < r; i++) {
    for(int j = 0; j <= k; j++) {
      mn = min(mn, solveL(l - 1, i, j) + solveR(i + 1, r + 1, k - j));
    }
  }

  cout << ans + mn << '\n';
}
 
int main() {
  setIO();

  auto solve = [&](int test_case)-> void {
    while(test_case--) {
      solve_();
    }
  };
 
  int test_cases = 1;
  // cin >> test_cases;
  solve(test_cases);
 
  return 0;
}

Compilation message

holding.cpp: In function 'void setIO(std::string)':
holding.cpp:83:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |     freopen((str + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
holding.cpp:84:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |     freopen((str + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 199896 KB Output is correct
2 Correct 89 ms 199924 KB Output is correct
3 Correct 91 ms 199888 KB Output is correct
4 Correct 90 ms 199884 KB Output is correct
5 Correct 92 ms 199824 KB Output is correct
6 Correct 90 ms 199820 KB Output is correct
7 Correct 95 ms 199884 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 199896 KB Output is correct
2 Correct 89 ms 199924 KB Output is correct
3 Correct 91 ms 199888 KB Output is correct
4 Correct 90 ms 199884 KB Output is correct
5 Correct 92 ms 199824 KB Output is correct
6 Correct 90 ms 199820 KB Output is correct
7 Correct 95 ms 199884 KB Output is correct
8 Correct 92 ms 199820 KB Output is correct
9 Correct 97 ms 199888 KB Output is correct
10 Correct 98 ms 199904 KB Output is correct
11 Correct 103 ms 199872 KB Output is correct
12 Correct 104 ms 199856 KB Output is correct
13 Correct 126 ms 199884 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 199896 KB Output is correct
2 Correct 89 ms 199924 KB Output is correct
3 Correct 91 ms 199888 KB Output is correct
4 Correct 90 ms 199884 KB Output is correct
5 Correct 92 ms 199824 KB Output is correct
6 Correct 90 ms 199820 KB Output is correct
7 Correct 95 ms 199884 KB Output is correct
8 Correct 92 ms 199820 KB Output is correct
9 Correct 97 ms 199888 KB Output is correct
10 Correct 98 ms 199904 KB Output is correct
11 Correct 103 ms 199872 KB Output is correct
12 Correct 104 ms 199856 KB Output is correct
13 Correct 126 ms 199884 KB Output is correct
14 Correct 101 ms 199824 KB Output is correct
15 Correct 91 ms 199840 KB Output is correct
16 Correct 123 ms 199856 KB Output is correct
17 Correct 99 ms 199896 KB Output is correct
18 Correct 95 ms 199884 KB Output is correct
19 Correct 124 ms 199812 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 199896 KB Output is correct
2 Correct 89 ms 199924 KB Output is correct
3 Correct 91 ms 199888 KB Output is correct
4 Correct 90 ms 199884 KB Output is correct
5 Correct 92 ms 199824 KB Output is correct
6 Correct 90 ms 199820 KB Output is correct
7 Correct 95 ms 199884 KB Output is correct
8 Correct 92 ms 199820 KB Output is correct
9 Correct 97 ms 199888 KB Output is correct
10 Correct 98 ms 199904 KB Output is correct
11 Correct 103 ms 199872 KB Output is correct
12 Correct 104 ms 199856 KB Output is correct
13 Correct 126 ms 199884 KB Output is correct
14 Correct 101 ms 199824 KB Output is correct
15 Correct 91 ms 199840 KB Output is correct
16 Correct 123 ms 199856 KB Output is correct
17 Correct 99 ms 199896 KB Output is correct
18 Correct 95 ms 199884 KB Output is correct
19 Correct 124 ms 199812 KB Output is correct
20 Correct 102 ms 199856 KB Output is correct
21 Correct 95 ms 199836 KB Output is correct
22 Correct 100 ms 199828 KB Output is correct
23 Correct 99 ms 199836 KB Output is correct
24 Correct 114 ms 199876 KB Output is correct
25 Correct 272 ms 199856 KB Output is correct