oj.uz

Submission #60145

# Submission time Handle Problem Language Result Execution time Memory
60145 2018-07-23T17:54:36 Z egorlifar Homecoming (BOI18_homecoming) C++17
100 / 100
 303 ms 96092 KB 
/*
ЗАПУСКАЕМ 
░ГУСЯ░▄▀▀▀▄░РАБОТЯГУ░░
▄███▀░◐░░░▌░░░░░░░
░░░░▌░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░▄▀▒▒▀▀▀▀▄
░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░▄▄▌▌▄▌▌░░░░░ 
 */
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <bits/stdc++.h>
#include "homecoming.h"
    
     
using namespace std;
template<typename T1, typename T2>inline void chkmin(T1 &x, T2 y) { if (x > y) x = y; }
template<typename T1, typename T2>inline void chkmax(T1 &x, T2 y) { if (x < y) x = y; } 
template<typename T, typename U> inline ostream &operator<< (ostream &_out, const pair<T, U> &_p) { _out << _p.first << ' ' << _p.second; return _out; }
template<typename T, typename U> inline istream &operator>> (istream &_in, pair<T, U> &_p) { _in >> _p.first >> _p.second; return _in; }
template<typename T> inline ostream &operator<< (ostream &_out, const vector<T> &_v) { if (_v.empty()) { return _out; } _out << _v.front(); for (auto _it = ++_v.begin(); _it != _v.end(); ++_it) { _out << ' ' << *_it; } return _out; }
template<typename T> inline istream &operator>> (istream &_in, vector<T> &_v) { for (auto &_i : _v) { _in >> _i; } return _in; }
template<typename T> inline ostream &operator<< (ostream &_out, const set<T> &_s) { if (_s.empty()) { return _out; } _out << *_s.begin(); for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) { _out << ' ' << *_it; } return _out; }
template<typename T> inline ostream &operator<< (ostream &_out, const multiset<T> &_s) { if (_s.empty()) { return _out; } _out << *_s.begin(); for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) { _out << ' ' << *_it; } return _out; }
template<typename T> inline ostream &operator<< (ostream &_out, const unordered_set<T> &_s) { if (_s.empty()) { return _out; } _out << *_s.begin(); for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) { _out << ' ' << *_it; } return _out; }
template<typename T> inline ostream &operator<< (ostream &_out, const unordered_multiset<T> &_s) { if (_s.empty()) { return _out; } _out << *_s.begin(); for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) { _out << ' ' << *_it; } return _out; }
template<typename T, typename U> inline ostream &operator<< (ostream &_out, const map<T, U> &_m) { if (_m.empty()) { return _out; } _out << '(' << _m.begin()->first << ": " << _m.begin()->second << ')'; for (auto _it = ++_m.begin(); _it != _m.end(); ++_it) { _out << ", (" << _it->first << ": " << _it->second << ')'; } return _out; }
template<typename T, typename U> inline ostream &operator<< (ostream &_out, const unordered_map<T, U> &_m) { if (_m.empty()) { return _out; } _out << '(' << _m.begin()->first << ": " << _m.begin()->second << ')'; for (auto _it = ++_m.begin(); _it != _m.end(); ++_it) { _out << ", (" << _it->first << ": " << _it->second << ')'; } return _out; }
#define sz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define left left228
#define right right228
#define next next228
#define rank rank228
#define prev prev228
#define y1 y1228                                                         
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define files(FILENAME) read(FILENAME), write(FILENAME)
#define pb push_back
const string FILENAME = "input";
const int MAXN = 2000228;
using int64 = long long;
 

struct Flow {
    int64 from, to, limit;
 
    Flow() = default;
    Flow(int64 from_, int64 to_, int64 limit_)
        : from(from_), to(to_), limit(limit_) {}
};
 

int64 solve(int n, int k, int* a_, int* b_) {
    vector<int64> a(n), b(n);
    for (int i = 0; i < n; ++i) {
        a[i] = a_[i];
        b[i] = b_[i];
    }
    int64 result = accumulate(all(a), 0LL);
    deque<Flow> flows;
    int64 start_layer = 0, end_layer = accumulate(b.begin(), b.begin() + k, 0LL);
    int64 pushed_front = 0, cycle_layer = 0;
    function<int64(int64)> PushBack = [&](int64 mx) -> int64 {
        int64 from = start_layer;
        if (not flows.empty() and from <= flows.back().to) {
            from = flows.back().to + 1;
        }
        if (mx > end_layer - from) {
            mx = end_layer - from;
        }
        if (mx <= 0) {
            return 0;
        }
        flows.emplace_back(from, from + mx - 1, end_layer);
        return mx;
    };
 
    function<int64(int64)> PushFront = [&](int64 mx) -> int64 {
        if (mx == 0) {
            return 0;
        }
        int64 r = pushed_front + mx - 1;
        int64 mn_move = 1LL << 62, sum_used = 0;
        while (not flows.empty() and flows.front().from <= r) {
            int64 dif = min(r - flows.front().from + 1,
            flows.front().limit - flows.front().to - 1);
            mx -= r - flows.front().from + 1 - dif;
            r = flows.front().to + dif;
            chkmin(mn_move, flows.front().limit - r - 1);
            sum_used += flows.front().to - flows.front().from + 1;
            flows.pop_front();
        }
        if (sum_used != 0) {
            flows.emplace_front(pushed_front + mx, pushed_front + mx + sum_used - 1, pushed_front + mx + sum_used + mn_move);
        }
        return mx;
    };
    for (int i = 0; i < n; ++i) {
        int64 pushed = PushBack(a[i]);
        a[i] -= pushed;
        result -= pushed;
        if (i + k > n) {
            cycle_layer  += b[(i + k - 1) % n];
            pushed_front += PushFront(min(a[i], cycle_layer - pushed_front));
        }
        start_layer += b[i];
        if (i + k < n) {
            end_layer += b[i + k];
        }
    }
    result -= pushed_front;
    return result;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 448 KB Output is correct
3 Correct 3 ms 448 KB Output is correct
4 Correct 3 ms 448 KB Output is correct
5 Correct 2 ms 448 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 448 KB Output is correct
3 Correct 3 ms 448 KB Output is correct
4 Correct 3 ms 448 KB Output is correct
5 Correct 2 ms 448 KB Output is correct
6 Correct 4 ms 600 KB Output is correct
7 Correct 3 ms 676 KB Output is correct
8 Correct 3 ms 676 KB Output is correct
9 Correct 3 ms 676 KB Output is correct
10 Correct 5 ms 676 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 24420 KB Output is correct
2 Correct 5 ms 24420 KB Output is correct
3 Correct 247 ms 96092 KB Output is correct
4 Correct 6 ms 96092 KB Output is correct
5 Correct 15 ms 96092 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 448 KB Output is correct
3 Correct 3 ms 448 KB Output is correct
4 Correct 3 ms 448 KB Output is correct
5 Correct 2 ms 448 KB Output is correct
6 Correct 4 ms 600 KB Output is correct
7 Correct 3 ms 676 KB Output is correct
8 Correct 3 ms 676 KB Output is correct
9 Correct 3 ms 676 KB Output is correct
10 Correct 5 ms 676 KB Output is correct
11 Correct 69 ms 24420 KB Output is correct
12 Correct 5 ms 24420 KB Output is correct
13 Correct 247 ms 96092 KB Output is correct
14 Correct 6 ms 96092 KB Output is correct
15 Correct 15 ms 96092 KB Output is correct
16 Correct 303 ms 96092 KB Output is correct
17 Correct 121 ms 96092 KB Output is correct
18 Correct 272 ms 96092 KB Output is correct
19 Correct 194 ms 96092 KB Output is correct
20 Correct 141 ms 96092 KB Output is correct
21 Correct 159 ms 96092 KB Output is correct