oj.uz

Submission #881600

# Submission time Handle Problem Language Result Execution time Memory
881600 2023-12-01T15:20:37 Z Iliya_ Fancy Fence (CEOI20_fancyfence) C++17
40 / 100
 20 ms 6236 KB 
//IN THE NAME OF GOD
#include<bits/stdc++.h>
#pragma GCC optimize("O2,unroll-loops")
#define endl        '\n'
#define F           first
#define S           second
#define pii         pair<int,int>
#define all(x)      x.begin(),x.end()
#define pb          push_back
#define fast_io     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define file_io     freopen("input.in" , "r" , stdin) ; freopen("output.out" , "w" , stdout);
using namespace std;
typedef long long ll; 
typedef long double dll;

#define int long long
const int N = 1e5+7, mod = 1e9+7;
int h[N], w[N], sumw[N], dp[N], ans[N], inv2; 
vector<pii> vec; 

int power(int a, int b){
     int ans = 1;
     while(b){
          if (b&1) ans = ans * a % mod; 
          a = a * a % mod; 
          b /= 2; 
     }
     return ans; 
}

int f(int x){
     return (x * (x-1) % mod * inv2 % mod);
}

int32_t main(){
     fast_io; 

     inv2 = power(2,mod-2); 
     int n; cin >> n; 
     for(int i=1; i<=n; i++) cin >> h[i]; 
     for(int i=1; i<=n; i++){
          cin >> w[i]; 
          sumw[i] = (sumw[i-1] + w[i]) % mod; 
     }
     dp[0] = ans[0] = 0;
     vec.pb({0,0}); 
     for(int i=1; i<=n; i++){
          while(vec.back().F >= h[i]) vec.pop_back();
          int ind = vec.back().S;
          vec.pb({h[i],i}); 
          int majw = sumw[i-1] - sumw[ind], majw2 = sumw[i] - sumw[ind];   
          dp[i] = (dp[ind] + f(h[i]+1) * majw2 % mod) %mod;
          ans[i] = (dp[ind] * w[i] % mod + f(h[i]+1) * f(w[i]+1) % mod + f(h[i]+1) * w[i] % mod * majw % mod)%mod; 
     }
     int out = 0; 
     for(int i=1; i<=n; i++) out = (out + ans[i]) % mod; 
     cout << out << endl;

     return 0;
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

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

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 8 ms 3164 KB Output is correct
4 Correct 15 ms 5468 KB Output is correct
5 Correct 16 ms 5344 KB Output is correct
6 Correct 15 ms 5468 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 3 ms 844 KB Output is correct
3 Correct 10 ms 3332 KB Output is correct
4 Correct 18 ms 6232 KB Output is correct
5 Correct 20 ms 6236 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 3 ms 860 KB Output is correct
4 Correct 9 ms 3380 KB Output is correct
5 Correct 18 ms 6228 KB Output is correct
6 Correct 19 ms 6236 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 2 ms 1368 KB Output is correct
9 Incorrect 10 ms 3680 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 1 ms 520 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -