Submission #1067363

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067363		slivajan	Flooding Wall (BOI24_wall)	C++17	70 / 100	5077 ms	111872 KiB

Main

#include <bits/stdc++.h>
using namespace std;

typedef long long un;
typedef vector<un> vuc;
typedef pair<un, un> pun;

#define REP(i, a, b) for (un i = (un)a; i < (un)b; i++)
#define REPR(i, a, b) for (un i = ((un)b)-1; i >= (un)a; i--)
#define FEAC(i, a) for (auto&& i : a)
#define vec vector
#define ALL(x) (x).begin(), (x).end()
#define DEB(x) cerr << #x << " = " << (x) << endl;

constexpr un MOD = 1e9 + 7;

vuc walls;
un M;

un i2w(un i){
    return walls[i];
}

un w2i(un w){
    return lower_bound(ALL(walls), w) - walls.begin();
}

int main(){
    un N;
    cin >> N;

    vuc A(N);
    vuc B(N);

    set<un> walls_set;

    REP(i, 0, N){
        cin >> A[i];
        walls_set.insert(A[i]);
    }

    REP(i, 0, N){
        cin >> B[i];
        walls_set.insert(B[i]);
    }

    walls_set.insert(1);

    FEAC(w, walls_set){
        walls.push_back(w);
    }
    M = walls.size();

    vuc vody(M, 0);
    vuc vysky(M, 0);
    vysky[0] = 1;

    REP(e, 0, N){
        vuc pref_vysky(M, 0);
        pref_vysky[M-1] = vysky[M-1];
        REPR(i, 0, M-1){
            pref_vysky[i] = pref_vysky[i+1] + vysky[i];
            pref_vysky[i] %= MOD;
        }

        vuc new_vysky(M, 0);
        vuc new_vody(M, 0);

        FEAC(val, vuc({w2i(A[e]), w2i(B[e])})){
            un counter = 0;
            REP(i, 0, val){
                counter += vysky[i];
                counter %= MOD;
            }
            
            new_vysky[val] += counter;
            new_vysky[val] %= MOD;

            REP(i, val, M){
                new_vysky[i] += vysky[i];
                new_vysky[i] %= MOD;
            }

            REP(i, 0, val){
                new_vody[i] += vody[val];
                new_vody[i] %= MOD;
            }
            
            un last_zvys = 0;
            REP(i, val, M){
                new_vody[i] += vody[i] + (i2w(i) - i2w(val)) * pref_vysky[i] + last_zvys;
                new_vody[i] %= MOD;

                last_zvys += (i2w(i) - i2w(val)) * vysky[i];
                last_zvys %= MOD;
            }

        }

        vysky = new_vysky;
        vody = new_vody;
    }

    cout << vody[0] << endl;

}

• Subtask 1: 8 / 8
• Subtask 2: 17 / 17
• Subtask 3: 19 / 19
• Subtask 4: 14 / 14
• Subtask 5: 12 / 12
• Subtask 6: 0 / 30