Submission #1170380

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170380		zaki98	Bouquet (EGOI24_bouquet)	C++20	100 / 100	24 ms	3572 KiB

Main

#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef long long ll;
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define pii pair<int,int>
#define pll pair<long long, long long>
// permutation of the last layer
#define LOO(i,a,b) for (int i = a; i <= b; i++)
#define max3(a, b, c) max(max(a, b), c)
#define min3(a, b, c) min(min(a, b), c)
using namespace std;
const ll MAX = 1e9 + 7;
void iO() {
    freopen("output.txt","w",stdout);
    freopen("input.txt","r",stdin);
}
vector<int> make_sorted_index(vector<int> const& values) {
    vector<int> index(values.size());
    iota(index.begin(), index.end(), 0);
    stable_sort(index.begin(), index.end(), [&values](int a, int b) { return values[a] < values[b]; } );
    return index;
} // this function is so skibidi

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
vector<pii> bouquet;

int n;

int solve() {
    cin >> n;
    bouquet = vector<pii>(n);
    vector<pii> evals(n, MP(0, -1e9));
    LOO(i, 0, n-1) {
        int a, b;
        cin >> a >> b;
        bouquet[i] = MP(a, b);
    }
    int maxy = 0;
    LOO(i, 0, n-1) {
        if (evals[i].S == -1e9) {
            evals[i] = MP(0, -1e9);
        }
        maxy = max(maxy, evals[i].F);
        if (evals[i].S < i - bouquet[i].F) {
            // we can play move
            int exit_index = i+bouquet[i].S + 1;
            maxy = max(maxy, evals[i].F + 1);
            if (exit_index < n) {
                if (evals[exit_index].S == -1e9) {
                evals[exit_index] = MP(evals[i].F + 1, i);
                }
                else {
                    // do comparaison
                    if (evals[i].F + 1 > evals[exit_index].F) {
                        evals[exit_index] = MP(evals[i].F + 1, i);
                    }
                    else if (evals[i].F + 1 == evals[exit_index].F && i < evals[exit_index].S) {
                        evals[exit_index] = MP(evals[i].F + 1, i);
                    }
                }
            }
        }
        if (i != n-1) {
            int exit_index = i + 1;
            if (evals[exit_index].S == -1e9) {
                evals[exit_index] = MP(evals[i].F, evals[i].S);
            }
                else {
                    // do comparaison
                    if (evals[i].F > evals[exit_index].F) {
                        evals[exit_index] = MP(evals[i].F, evals[i].S);
                    }
                    else if (evals[i].F == evals[exit_index].F && evals[i].S < evals[exit_index].S) {
                        evals[exit_index] = MP(evals[i].F, evals[i].S);
                    }
                }
        }
    }
    cout << maxy << '\n';
    return 0;
  }
   


int main() {
   ios_base::sync_with_stdio(false);
    cin.tie(NULL);
  //  iO();
    //pre_process();
    int t = 1;
  // cin >> t;
    while (t--) {
        solve();
       // cout << flush;
    }
}

Compilation message (stderr)

Main.cpp: In function 'void iO()':
Main.cpp:18:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     freopen("output.txt","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:19:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     freopen("input.txt","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 16 / 16
• Subtask 3: 28 / 28
• Subtask 4: 18 / 18
• Subtask 5: 30 / 30