#include <bits/stdc++.h>
using namespace std;
bool cmp(pair<int, int> a, pair<int, int> b){
if(a.first != b.first) return a.first > b.first;
else return a.second > b.second;
}
int main(){
cin.tie(0);ios::sync_with_stdio(0);
//1.
int n, m;
bool eg = 1;
//2.
cin >> n >> m;
long long int a[n], b[n];
pair <int, int> c[n];
//3.
for(int i = 0; i < n; i++) cin >> c[i].first;
for(int i = 0; i < n; i++){
cin >> c[i].second;
if(c[i].first != c[i].second) eg = 0;
if(c[i].first < c[i].second) c[i].first = c[i].second;
}
long long int v[n][m + 1];
sort(c + 0, c + n, cmp );
for(int i = 0; i < n; i++){
a[i] = c[i].first;
b[i] = c[i].second;
}
/*
cout << "b : ";
for(int i = 0; i < n; i++) cout << b[i] << " ";
cout << endl;
*/
for(int i = 0; i < n; i++){
for(int j = 0; j <= m; j++) v[i][j] = 0;
}
/*
cout << "a : ";
for(int i = 0; i < n; i++) cout << a[i] << " ";
cout << endl;
cout << "b : ";
for(int i = 0; i < n; i++) cout << b[i] << " ";
cout << endl;
*/
for(int j = 1; j <= m; j++){
//cout << "Suntem la ziua " << j << endl;
priority_queue< pair<long long int, long long int>,
vector< pair<long long int, long long int> >,
greater< pair<long long int, long long int> > > q;
long long int mini = LLONG_MAX;
for(int i = 0; i < n; i++){
mini = min(mini, v[i][j - 1]);
}
int spare = 0;
for(int i = 0; i < n; i++){
//cout << " -- > nr " << v[i][j] << " mini = " << mini << endl;
if(v[i][j - 1] == mini){
//cout << " -- > mai add un " << a[i] << endl;
v[i][j] = v[i][j - 1] + a[i];
}else{
v[i][j] = v[i][j - 1];
spare++;
//cout << " -- > lasam spare" << endl;
}
q.push( make_pair( v[i][j] , i ) );
}
while(!q.empty() && spare > 0){
//cout << " -- > q.top() = " << q.top().first << " " << q.top().second << endl;
int p = q.top().second;
q.pop();
long long int nx = v[p][j] + 1;
if(!q.empty()) nx = q.top().first;
while(v[p][j] <= nx && spare > 0){
if(v[p][j] == v[p][j - 1]){
//cout << " -- > C1" << endl;
v[p][j] += a[p];
}else{
v[p][j] += b[p];
//cout << " -- > b[p] = " << b[p] << endl;
//cout << " -- > C2" << endl;
}
spare--;
}
//q.pop();
}
//cout << " -- > v[" << j << "] : ";
//for(int i = 0; i < n; i++) cout << v[i][j] << " ";
//cout << endl;
//cout << " brk";
}
//cout << "iesit" << endl;
long long int mini = LLONG_MAX;
for(int i = 0; i < n; i++) mini = min(mini, v[i][m]);
cout << mini << endl;
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:15:10: warning: variable 'eg' set but not used [-Wunused-but-set-variable]
15 | bool eg = 1;
| ^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 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 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
604 KB |
Output is correct |
11 |
Correct |
94 ms |
21684 KB |
Output is correct |
12 |
Correct |
92 ms |
21192 KB |
Output is correct |
13 |
Correct |
56 ms |
22468 KB |
Output is correct |
14 |
Correct |
57 ms |
21936 KB |
Output is correct |
15 |
Correct |
0 ms |
344 KB |
Output is correct |
16 |
Correct |
48 ms |
22728 KB |
Output is correct |
17 |
Correct |
72 ms |
28056 KB |
Output is correct |
18 |
Correct |
95 ms |
27588 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
48 ms |
22728 KB |
Output is correct |
3 |
Correct |
72 ms |
28056 KB |
Output is correct |
4 |
Correct |
95 ms |
27588 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 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 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
604 KB |
Output is correct |
11 |
Correct |
94 ms |
21684 KB |
Output is correct |
12 |
Correct |
92 ms |
21192 KB |
Output is correct |
13 |
Correct |
56 ms |
22468 KB |
Output is correct |
14 |
Correct |
57 ms |
21936 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
17 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 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 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
604 KB |
Output is correct |
11 |
Correct |
94 ms |
21684 KB |
Output is correct |
12 |
Correct |
92 ms |
21192 KB |
Output is correct |
13 |
Correct |
56 ms |
22468 KB |
Output is correct |
14 |
Correct |
57 ms |
21936 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
17 |
Halted |
0 ms |
0 KB |
- |