oj.uz

Submission #502434

# Submission time Handle Problem Language Result Execution time Memory
502434 2022-01-06T02:01:25 Z Fireball0424 Fancy Fence (CEOI20_fancyfence) C++14
30 / 100
 434 ms 262148 KB 
#include <bits/stdc++.h>
#define int long long
#define fr first
#define sc second
#define pii pair<int,int>
using namespace std;

const int mod = 1e9 + 7;

int modpow(int a, int b){
    if(b == 0) return 1;
    int res = modpow(a, b / 2);
    res = (res * res) % mod;
    if(b & 1) res = (res * a) % mod;
    return res;
}

int cal(int h, int w){
    w = max(0LL, w) % mod;
    int res = h * (h + 1) % mod;
    res = (res * w) % mod;
    res = (res * (w + 1)) % mod;
    res = (res * modpow(4, mod - 2)) % mod;
    return max(0LL, res);
}

void solve(){
    int n;
    cin >> n;
    vector<int> h(n + 1, 0), w(n + 1, 0);
    for(int i = 1; i <= n; ++i) cin >> h[i];
    for(int i = 1; i <= n; ++i) cin >> w[i];
    vector<vector<int> > min_h(n + 1, vector<int>(n + 1, INT_MAX));
    vector<int> pre_w(n + 1, 0);
    for(int i = 1; i <= n; ++i){
        pre_w[i] = pre_w[i-1] + w[i];
        for(int j = i; j <= n; ++j){
            min_h[i][j] = min(min_h[i][j-1], h[j]);
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; ++i){
        for(int j = i; j <= n; ++j){
            ans += cal(min_h[i][j], pre_w[j] - pre_w[i-1]);
            //cout << ans << ' ';
            ans -= cal(min_h[i][j], pre_w[j] - pre_w[i-1] - w[i]);
            //cout << ans << ' ';
            ans -= cal(min_h[i][j], pre_w[j] - pre_w[i-1] - w[j]);
            //cout << ans << ' ';
            ans += cal(min_h[i][j], pre_w[j] - pre_w[i-1] - w[j] - w[i]);
            ans = (ans + mod) % mod;
            //cout << ans << endl;
        }
    }
    cout << ans << endl;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    //freopen("bbreeds.in", "r");
    //freopen("bbreeds.out", "w");
    solve();
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 412 ms 8216 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 312 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 407 ms 8200 KB Output is correct
3 Runtime error 103 ms 262148 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 420 ms 8140 KB Output is correct
2 Runtime error 99 ms 262148 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 316 KB Output is correct
2 Correct 434 ms 8212 KB Output is correct
3 Runtime error 98 ms 262148 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 426 ms 8208 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 2 ms 308 KB Output is correct
8 Correct 416 ms 8140 KB Output is correct
9 Correct 408 ms 8212 KB Output is correct
10 Correct 414 ms 8216 KB Output is correct
11 Correct 5 ms 332 KB Output is correct
12 Correct 101 ms 2236 KB Output is correct
13 Correct 401 ms 8236 KB Output is correct
14 Correct 429 ms 8252 KB Output is correct
15 Correct 407 ms 8216 KB Output is correct
16 Correct 0 ms 204 KB Output is correct

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 412 ms 8216 KB Output is correct
3 Correct 0 ms 288 KB Output is correct
4 Correct 430 ms 8208 KB Output is correct
5 Correct 1 ms 288 KB Output is correct
6 Correct 1 ms 312 KB Output is correct
7 Correct 1 ms 292 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 2 ms 312 KB Output is correct
10 Correct 413 ms 8252 KB Output is correct
11 Runtime error 102 ms 262148 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -