#include <bits/stdc++.h>
// #include <tr2/dynamic_bitset>
using namespace std;
// using namespace tr2;
#pragma GCC optimize("O3,unroll-loops,Ofast")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
const long double eps = 1e-9;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int randgen(int left, int right) {
return uniform_int_distribution<int>(left, right)(rng);
}
long long randgenll(long long left, long long right) {
return uniform_int_distribution<long long>(left, right)(rng);
}
typedef long long ll;
typedef long double ld;
const int mod = 1e9 + 7;
struct Mint
{
int val;
Mint(int x = 0)
{
val = x % mod;
}
Mint(long long x)
{
val = x % mod;
}
Mint operator+(Mint oth)
{
return val + oth.val;
}
Mint operator*(Mint oth)
{
return 1LL * val * oth.val;
}
Mint operator-(Mint oth)
{
return val - oth.val + mod;
}
Mint fp(Mint a, long long n){
Mint p = 1;
while(n){
if(n & 1){
p = p * a;
}
a = a * a;
n /= 2;
}
return p;
}
Mint operator/(Mint oth){
Mint invers = fp(oth, mod - 2);
return 1LL * val * invers.val;
}
friend ostream& operator << (ostream& os, const Mint& lol){
os << lol.val;
return os;
}
};
struct AINT{
vector<ll> aint;
vector<ll> lazy;
AINT(int n){
aint.assign(n * 4 + 1,-1e9);
//lazy.assign(n * 4 + 1, -1);
}
void update(int v, int tl, int tr, int pos, int val){
if(tl == tr){
aint[v] = val;
return;
}
int tm = (tl + tr) / 2;
if(pos <= tm) update(v * 2, tl ,tm, pos, val);
else update(v * 2 + 1, tm + 1, tr, pos,val);
aint[v] = max(aint[v * 2], aint[v * 2 + 1]);
}
int query(int v, int tl, int tr, int l, int r){
int tm = (tl + tr) / 2;
if(l <= tl && r >= tr) return aint[v];
if(l > tr || r < tl) return -1e9;
return max(query(v * 2, tl, tm,l,r), query(v * 2 + 1, tm + 1, tr, l,r));
}
};
struct AIB{
vector<int> aib;
AIB(int n){
aib.assign(n + 1,0);
}
void update(int pos, int val){
for(; pos < aib.size(); pos += (pos & -pos)){
aib[pos] += val;
}
}
int query(int pos){
int pl = 0;
for(; pos > 0; pos -= (pos & -pos)) pl += aib[pos];
return pl;
}
};
int red = 0;
int ______________________________________________________________________________________________________________________________________________;
long long solve(int n, int k, int *a, int *b){
long long prof = 0;
vector<int> luate(n + 1), luat(n + 1);
for(int i = 0; i < n; i++){
long long maxim = -1e18;
int nd = -1;
for(int j = 0; j < n; j++){
if(!luat[j]){
long long sm = 0;
for(int l = 1; l <= k; l++){
int pos = (j + l - 1) % n;
sm -= ((!luate[pos]) * b[pos]);
}
sm += a[j];
if(maxim < sm){
maxim = sm;
nd = j;
}
}
}
if(maxim < 0){
break;
}else{
prof += maxim;
luat[nd] = 1;
for(int j = 1; j <= k; j++){
luate[(nd + j - 1) % n] = 1;
}
}
}
return prof;
}
// int32_t main(){
// cin.tie(0)->sync_with_stdio(0);
// // int t = 1;
// // if(red) cin >> t;
// // while(t--){
// // solve();
// // }
// int a[3] = {40,80,100};
// int b[3] = {140,0,20};
// cout << solve(3,2,a,b);
// }
/*
4 1
0 0 1
j + 1 + p >= d
p >= d - j - 1
i + j >= d
j >= d - i;
*/
Compilation message
homecoming.cpp: In member function 'void AIB::update(int, int)':
homecoming.cpp:99:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | for(; pos < aib.size(); pos += (pos & -pos)){
| ~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1012 ms |
17736 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
