oj.uz

Submission #750699

# Submission time Handle Problem Language Result Execution time Memory
750699 2023-05-30T07:27:01 Z inventiontime Fancy Fence (CEOI20_fancyfence) C++17
30 / 100
 1000 ms 8028 KB 
#include <bits/stdc++.h>
using namespace std;

#define int ll
#define endl '\n' //comment for interactive
#define fast_io ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)

#define pb push_back
#define re resize
#define ff first
#define ss second

#define all(x) (x).begin(), (x).end()
#define all1(x) (x).begin()+1, (x).end()
#define loop(i, n) for(int i = 0; i < n; i++)
#define loop1(i, n) for(int i = 1; i <= n; i++)

#define print(x) cout << #x << ": " << x << endl << flush

typedef long long ll;
typedef vector<int> vi;
typedef array<int, 2> ii;
typedef array<int, 3> ti;
typedef vector<ii> vii;
typedef vector<ti> vti;
typedef vector<vi> vvi;
typedef priority_queue<int> pq;

template<class T> bool ckmin(T&a, T b) { bool B = a > b; a = min(a, b); return B; }
template<class T> bool ckmax(T&a, T b) { bool B = a < b; a = max(a, b); return B; }

const int inf = 1e17;
const int mod = 1e9+7;

int power(ll x, int y) {
    int res = 1;

    x = x % mod;

    while(y > 0) {
        if(y & 1)
            res = ((ll)res*x) % mod;

        y = y >> 1;
        x = (x*x) % mod;
    }

    return res;
}

int inv(int n) {
    return power(n, mod-2);
}

int mm(int x, int y) {
    x %= mod, y %= mod;
    return (x * y) % mod;
}

int nc2(int n) {
    return mm(mm(n, (n-1)), inv(2));
}

void solve() {

    int n;
    cin >> n;
    vi h(n+1), w(n+1);
    loop1(i, n)
        cin >> h[i];
    loop1(i, n)
        cin >> w[i];
    vi pw(n+1);
    loop1(i, n) {
        pw[i] = pw[i-1] + w[i];
        pw[i] %= mod;
    }

    auto calc = [&] (int l, int r, auto calc) -> int {
        if(r < l) return 0;
        ii minh = {inf, inf};
        for(int i = l; i <= r; i++) 
            ckmin(minh, {h[i], i});
        auto [mh, mi] = minh;
        return
            (mm(nc2(mh+1), nc2(w[mi] + 1))
            + mm(nc2(mh+1), mm(pw[mi-1] - pw[l-1], w[mi]))
            + mm(nc2(mh+1), mm(pw[r] - pw[mi], w[mi]))
            + mm(nc2(mh+1), mm(pw[mi-1] - pw[l-1], pw[r] - pw[mi]))
            + calc(l, mi-1, calc) 
            + calc(mi+1, r, calc)) % mod;
    };
    
    cout << ((calc(1, n, calc) + mod) % mod) << endl;

}

signed main() {

    fast_io;

    int t = 1; //cin >> t;
    while(t--)
        solve();

    return 0;

}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Execution timed out 1067 ms 2672 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 41 ms 1700 KB Output is correct
3 Correct 861 ms 8028 KB Output is correct
4 Execution timed out 1071 ms 6436 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 39 ms 1716 KB Output is correct
4 Correct 870 ms 7840 KB Output is correct
5 Execution timed out 1059 ms 6340 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 292 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 356 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 212 KB Output is correct

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Execution timed out 1083 ms 2864 KB Time limit exceeded
12 Halted 0 ms 0 KB -