oj.uz

Submission #447080

# Submission time Handle Problem Language Result Execution time Memory
447080 2021-07-24T12:04:52 Z Yahli Fancy Fence (CEOI20_fancyfence) C++14
58 / 100
 265 ms 262148 KB 
#include <bits/stdc++.h>
#define int long long

using namespace std; 
using pi = pair<int, int>; 

const int mod = 1e9+7; 
const int inv4 = 25e7+2; 

int calc(int a, int b){
    return ((a*(a+1)%mod)*(b*(b+1)%mod)%mod)*inv4%mod;
}

int req_solve(const vector<pi> & data, int n, int floor){
    if (n == 0) return 0; 

    //find the minimum: 
    int ind = 0, w = 0; 
    for (int i = 0; i < n; ++i){
        if (data[i].first < data[ind].first) ind = i; 
        w += data[i].second; 
    } 
    w %= mod; 

    int res = (calc(data[ind].first, w) - calc(floor, w) + mod) % mod;
    
    vector<pi> next; 
    for (int i = 0; i < n; ++i){
        if (data[i].first == data[ind].first){
            res = (req_solve(next, next.size(), data[ind].first) + res) % mod; 
            next.resize(0); 
        }
        else next.push_back(data[i]);
    }
    return (req_solve(next, next.size(), data[ind].first) + res) % mod; 
}

int32_t main(){
    int n; cin >> n;
    vector<pi> data(n); 
    for (int i = 0; i < n; ++i) cin >> data[i].first; 
    for (int i = 0; i < n; ++i) cin >> data[i].second; 
    cout << req_solve(data, n, 0); 
}

Subtask #1
0.0 / 0.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 32 ms 1580 KB Output is correct
4 Correct 65 ms 2992 KB Output is correct
5 Correct 63 ms 3008 KB Output is correct
6 Correct 63 ms 2992 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 9 ms 660 KB Output is correct
3 Correct 44 ms 2032 KB Output is correct
4 Correct 92 ms 3780 KB Output is correct
5 Correct 91 ms 3892 KB Output is correct
6 Correct 0 ms 296 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 10 ms 656 KB Output is correct
4 Correct 45 ms 1944 KB Output is correct
5 Correct 86 ms 3752 KB Output is correct
6 Correct 91 ms 3880 KB Output is correct
7 Correct 8 ms 10568 KB Output is correct
8 Runtime error 265 ms 262148 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 300 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 9 ms 10572 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 2 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 2 ms 332 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 0 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 288 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 35 ms 1588 KB Output is correct
12 Correct 63 ms 3024 KB Output is correct
13 Correct 62 ms 2988 KB Output is correct
14 Correct 62 ms 2984 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 9 ms 652 KB Output is correct
17 Correct 46 ms 1992 KB Output is correct
18 Correct 89 ms 3756 KB Output is correct
19 Correct 91 ms 3880 KB Output is correct
20 Correct 8 ms 10572 KB Output is correct
21 Runtime error 261 ms 262148 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -