Submission #1108214

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108214		matu	Homecoming (BOI18_homecoming)	C++17	0 / 100	1034 ms	8264 KiB

homecoming

#include <bits/stdc++.h>
// #include <tr2/dynamic_bitset>
#include "homecoming.h"
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;
    long long ans = -1e18;
    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;
                }
            }
        }
        prof += maxim;
        luat[nd] = 1;
        for(int j = 1; j <= k; j++){
            luate[(nd + j - 1) % n] = 1;
        }
        ans = max(ans, prof);
    }
    return ans;
}
// 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] = {1000,0,100};
//     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 (stderr)

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)){
      |               ~~~~^~~~~~~~~~~~

• Subtask 1: 0 / 13
• Subtask 2: 0 / 18
• Subtask 3: 0 / 31
• Subtask 4: 0 / 38