Submission #942349

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
942349	2024-03-10T13:30:32 Z	batsukh2006	Fancy Fence (CEOI20_fancyfence)	C++17	30 / 100	1000 ms	1628 KB

fancyfence

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<map>
#include<string>
#include<algorithm>
#include<vector>
#include<string.h>
#include<utility>
#include<set>
#include<cmath>
#include<queue>
#include<deque>
#include<functional>
#include<stack>
#include<limits.h>
#include<iomanip>
#include<unordered_map> 
 
using namespace std;
 
#define MOD 1000000007
#define int long long
#define endl '\n'
int cal(int a, int b){
    int f=(a*(a+1))%MOD*((MOD+1)/2)%MOD;
    int s=(b*(b+1))%MOD*((MOD+1)/2)%MOD;
    return (f*s)%MOD;
}
void solve(){
    int n; cin>>n;
    vector<int> h(n+1),w(n+1);
    for(int i=1; i<=n; i++) cin>>h[i];
    for(int i=1; i<=n; i++) cin>>w[i];
    int ans=0;
    for(int i=1; i<=n; i++){
        int cur=0,mx=h[i];
        ans=(ans+cal(h[i],w[i]))%MOD;
        for(int j=i-1; j>=1; j--){
            mx=min(mx,h[j]);
            cur=(cur+w[j])%MOD;
            ans=(ans-cal(cur,mx)+MOD)%MOD;
            ans=(ans+cal((cur+w[i])%MOD,mx))%MOD;
            ans=(ans+cal((cur-w[j])%MOD,mx))%MOD;
            ans=(ans-cal((w[i]+(cur-w[j])%MOD)%MOD,mx)+MOD)%MOD;
        }
    }
    cout<<ans;
}
signed main(){
	// freopen("hps.in", "r", stdin);
	// freopen("hps.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int t=1;
	// cin>>t;
	while(t--){
		solve();
		cout<<endl;
	}
	return 0;
}

Subtask #1

0.0 / 0.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	19 ms	464 KB	Output is correct

Subtask #2

12.0 / 12.0

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

Subtask #3

0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	16 ms	468 KB	Output is correct
3	Execution timed out	1070 ms	1628 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

Subtask #4

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	604 KB	Output is correct
2	Execution timed out	1028 ms	600 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #5

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	17 ms	348 KB	Output is correct
3	Execution timed out	1062 ms	800 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

Subtask #6

18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	16 ms	476 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
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	16 ms	604 KB	Output is correct
9	Correct	16 ms	348 KB	Output is correct
10	Correct	16 ms	344 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	4 ms	476 KB	Output is correct
13	Correct	16 ms	348 KB	Output is correct
14	Correct	16 ms	348 KB	Output is correct
15	Correct	16 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct

Subtask #7

0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	19 ms	464 KB	Output is correct
3	Correct	1 ms	344 KB	Output is correct
4	Correct	16 ms	348 KB	Output is correct
5	Correct	1 ms	344 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	344 KB	Output is correct
10	Correct	16 ms	600 KB	Output is correct
11	Execution timed out	1086 ms	1624 KB	Time limit exceeded
12	Halted	0 ms	0 KB	-