oj.uz

Submission #882442

# Submission time Handle Problem Language Result Execution time Memory
882442 2023-12-03T07:45:59 Z vjudge1 Bali Sculptures (APIO15_sculpture) C++17
0 / 100
 1 ms 500 KB 
#include <bits/stdc++.h>
#define fast cin.tie(0)->sync_with_stdio(0);
#define int long long
#define inf ((int)1e18)
using namespace std;

int32_t main(){
	fast
	int n, a, b;
	cin >> n >> a >> b;
	vector <int> arr(n + 1), p(n + 1);
	int sum = 0;
	for(int i = 1; i <= n; i++) {
		cin >> arr[i];
		p[i] = p[i-1];
		p[i] += arr[i];
	}
	vector <int> pst, pref, suf;
	pst.push_back(1),pst.push_back(n + 1), pref.push_back(p[n]), suf.push_back(p[n]);
	int ans = p[n];
	for(int part = 1; part <= b; part++) {
		int l = 0, wans = inf, windex, f, s;
		for(int ind = 1; ind <= n; ind++) {
			if(ind == pst[l]) {
				l++;
				continue;
			}
			int befor = l > 1 ? pref[l - 2] : 0;
			int afor = l < part ? suf[l] : 0;
			int st = pst[l-1], nd = pst[l];
			int first = (p[ind - 1] - p[st - 1]);
			int second = (p[nd - 1] - p[ind - 1]);
			int tans = befor | afor | first | second;
			// cout << ind << " " << befor << " " << afor << " " << first << " " << second << "\n";
 			if(tans < wans) {
 				wans = tans;
 				windex = ind;
 				f = first;
 				s = second;
 			}
 		}
 		// cout << wans << " " << windex << "\n";
 		ans = min(ans, wans);
 		// burdan böl şimdi
 		// update pst, pref, suf
 		vector <int> npst, npref, nsuf;
 		bool flag = 1;
 		for(int i = 0; i < part; i++) {
 			npst.push_back(pst[i]);
 			if(pst[i + 1] > windex and flag) {
 				npst.push_back(windex);
 				flag = 0;
 			}
 		}
 		npst.push_back(n+1);
 		pst = npst;
 		int prev = 0, prange = 0;
 		for(int i = 0; i < pst.size(); i++) {
 			int it = pst[i];
 			if(prev) {
 				npref.push_back((p[it-1] - p[prev-1]) | prange);
 				prange = p[it-1] - p[prev-1];
 			}
 			prev = it;
 		}
 		pref = npref;
 		prev = 0, prange = 0;
 		for(int i = pst.size()-1; i>=0; i--) {
 			int it = pst[i];
 			if(prev) {
 				nsuf.push_back(p[prev-1] - p[it-1] | prange);
 				prange = p[prev-1] - p[it-1];
 			}
 			prev = it;
 		}
 		reverse(nsuf.begin(), nsuf.end());
 		suf = nsuf;
 		// for(auto it:pref) {
 		// 	cout << it << " ";
 		// }
 		// cout << "\n";
 		// for(auto it:suf) {
 		// 	cout << it << " ";
 		// }
 		// cout << "\n";
 		// for(auto it:pst) {
 		// 	cout << it << " ";
 		// }
 		// cout << "\n\n";
	}
	cout << ans << "\n";
}

Compilation message

sculpture.cpp: In function 'int32_t main()':
sculpture.cpp:58:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |    for(int i = 0; i < pst.size(); i++) {
      |                   ~~^~~~~~~~~~~~
sculpture.cpp:71:31: warning: suggest parentheses around arithmetic in operand of '|' [-Wparentheses]
   71 |      nsuf.push_back(p[prev-1] - p[it-1] | prange);
sculpture.cpp:22:34: warning: variable 'f' set but not used [-Wunused-but-set-variable]
   22 |   int l = 0, wans = inf, windex, f, s;
      |                                  ^
sculpture.cpp:22:37: warning: variable 's' set but not used [-Wunused-but-set-variable]
   22 |   int l = 0, wans = inf, windex, f, s;
      |                                     ^
sculpture.cpp:12:6: warning: unused variable 'sum' [-Wunused-variable]
   12 |  int sum = 0;
      |      ^~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 1 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 500 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -