#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e9;
/*
struct segtree{
int n;
vector<int> st, t, marked;
vector<array<int, 2>> x;
int base = 0;
segtree(int _n){
n = _n;
st.resize(4*n, 0);
t.resize(4*n, 0);
marked.resize(4*n, 0);
x.resize(4*n, 0);
}
void update(int v, int l, int r, int val){
push(v, l, r);
if(l>tr || r <tl) return;
if(l>=tl && r<=tr){
st[v]+=val; t[v] =val;
marked[v] = 1;
}
else{
int mid = (l+r) / 2;
update(v*2, l, mid, val);
update(v*2, mid, l, 1);
}
}
}
*/
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n; cin >> n;
vector<int> l(n), x(n);
vector<array<int, 2>> gh(n);
for(int i=0; i<n; i++) cin >> gh[i][0];
for(int i=0; i<n; i++) cin >> gh[i][1];
sort(gh.begin(), gh.end());
for(int i=0; i<n; i++) x[i] = gh[i][0], l[i] = gh[i][1];
vector<int> ans(n+1, -1), ind(n+1, -1);
ans[0] = 0;
int pos = 0;
for(int i=0; i<n; i++){
vector<int>pref;
pref = ans;
for(int l=1; l<=pos; l++){
pref[l]+=pref[l-1];
}
if(pref[pos] <= l[i]){
ans[pos+1] = x[i];
ind[pos+1] = i;
pos++;
}
else{
vector<int> pans, pind;
int el = i;
int sum = pref[pos]+x[i];
int ps =-1;
for(int j=1; j<=pos; j++){
if(sum-x[ind[j]]<=l[ind[j]]){
ps = j;
}
}
if(ps!=-1){
pans.push_back(0); pind.push_back(0);
sum = 0;
for(int j=1; j<=pos; j++){
if(ps==ind[j]) continue;
if(sum+ans[j]<= l[i]){
pans.push_back(ans[j]);
pind.push_back(ind[j]);
sum+=ans[j];
}
else if(sum <= l[i]){
pans.push_back(ans[i]);
pind.push_back(i);
pans.push_back(ans[j]);
pind.push_back(ind[j]);
sum+=x[i];
sum+=ans[j];
}
else{
pans.push_back(ans[j]);
pind.push_back(ind[j]);
sum+=ans[j];
}
}
pans.push_back(ans[ps]);
pind.push_back(ind[ps]);
sum = 0;
int flag = 1;
for(int i=0; i<=pans.size(); i++){
if(sum>l[pind[i]]) flag = 0;
sum+=pans[i];
}
if(flag){
for(int i=0; i<=pos+1; i++){
ans[i] = pans[i];
ind[i] = ind[i];
}
pos++;
}
}
}
}
cout << pos;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:118:31: 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]
118 | for(int i=0; i<=pans.size(); i++){
| ~^~~~~~~~~~~~~
Main.cpp:78:17: warning: unused variable 'el' [-Wunused-variable]
78 | int el = i;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
452 KB |
Output is correct |
| 3 |
Correct |
0 ms |
452 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 |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2045 ms |
30548 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
452 KB |
Output is correct |
| 3 |
Correct |
0 ms |
452 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 |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
452 KB |
Output is correct |
| 3 |
Correct |
0 ms |
452 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 |
- |
