oj.uz

답안 #1008060

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1008060 2024-06-26T07:05:18 Z GTA Fancy Fence (CEOI20_fancyfence) C++17
30 / 100
 142 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define ld long double
#define pb push_back
#define endl '\n'
#define all(v) v.begin(), v.end()
#define all1(v) v.begin() + 1, v.end()
#define rall(v) v.rbegin(), v.rend()
#define rall1(v) v.rbegin(), v.rend()-1
#define fr(m,n,k) for(int m=n;m<=k;m++)
#define frr(m,n,k) for(int m=n;m>=k;m--)
#define yes cout << "YES"
#define no cout << "NO"
#define yesm cout << "Yes"
#define nom cout << "No"
#define inf 1e18
#define ext {cout << -1; return;}
#define zxt {cout << 0; return;}
#define noxt {no;return;}
#define yesxt {yes;return;}
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a*(b/gcd(a,b)))
#define fill(x,s) memset(x, s, sizeof(x));
#define lb lower_bound
#define ub upper_bound
#define pi pair<int,int>
#define vi vector<int>
#define vvi vector<vi>
#define vs vector<string>
#define vpi vector<pi>
#define mii map<int,int>
#define si set<int>
#define fi first
#define se second
#define sz size()
#define el cout<<endl

int mod = 1e9 + 7;
// int mod = 998244353;

int ft(int n) {int ans = 1; for (int i = 1; i <= n; ++i) {ans = ans * i;} return ans;}
int binpow(int x, int y) {if (y == 0) return 1; int z = 1; while (y) {  if (y & 1) z = z * x % mod; x = x * x % mod; y >>= 1;} return z;}
int inv(int x) {return binpow(x, mod - 2);}
int bintoint(string s) {reverse(all(s)); int xx = 0; int m = 1; int z = s.sz; fr(j, 0, z) {xx += (s[j] == '1' ? m : 0); m <<= 1;} return xx;}
string inttobin(int x) {if (x == 0) return "0"; string s; while (x) {s += (x & 1) + '0'; x >>= 1;} reverse(all(s)); return s;}
string ads(string s, string p) {if (s.sz > p.sz) swap(s, p); int n = s.sz, m = p.sz; reverse(all(s)); reverse(all(p)); int tm = 0; string st; fr(i, 0, n - 1) {tm = s[i] - '0' + p[i] - '0' + tm; st += '0' + tm % 10; tm /= 10;} fr(i, n, m - 1) {tm = p[i] - '0' + tm; st += '0' + tm % 10; tm /= 10;} if (tm != 0) {st += '0' + tm % 10;} reverse(all(st)); return st;}

bool id, id1, id2;
int n, m, k, l, r, a, b, c, d, e, x, y, z, i, j, q, t, o;
int mi = inf, ma, sum, ans, num, cnt;
string s, p;

const int N = 3e5 + 5;
void solve() {
	cin >> n; vi h(n + 1), w(n + 1);
	int mi[n + 1][n + 1];
	fr(i, 1, n) cin >> h[i]; fr(i, 1, n) cin >> w[i];
	int iv = inv(2);

	fr(i, 1, n) {
		int now = h[i];
		mi[i][i] = now;
		ans += now % mod * (now + 1) % mod * iv % mod * w[i] % mod * (w[i] + 1) % mod * iv % mod; ans %= mod;
		fr(j, i + 1, n) {
			now = min(now, h[j]);
			mi[i][j] = now;
			int ad = now * (now + 1) % mod * iv % mod; ad %= mod;
			ans += ad * w[i] % mod * w[j] % mod; ans %= mod;
		}
	}
	cout << ans;
}
signed main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(0);
	int T = 1;
	// cin >> T;
	for (; T--;) {
		cout << fixed << setprecision(5); solve();
		cout << endl;
	} return 0;
}
// Tc, angka kecil), No Overthink(trivial tp modified),
// Check Kasus Khusus(1,2,1e18), ganti jd bentuk lain (2 case or etc)
// bedah 1 1 variable yg bisa dicari, cari dari jwbn ke ques

// Sorting : Iterate Greedy (pake data struct) / dp / binser
// Graphs / Tree : DFS / adj / dis[a][b] != dis[a][c] + dis[c][b] / indegree
// Yang keliatan kyk dp : bisa jd brute force doang
// Data Structure : BIT / DSU / Segtree, SparseT / dequeue
// Compression, Line Sweep
// Parity (2 or 3, mod 4..) klo dilakuin 2 kali jadi sama aja -> parity mod 2

/*
brute force, greedy, pref sum, 2pointer, gcd/lcm, even/odd
min/max, binser, bfs/dfs, iterate, multiple/divisor

bipartite graph,bitmasking, sliding window, konstanta
divconquer, djikstra, stack(prev and next smaller)
prefix difference
*/

// tools :
//__lg(x),__builtinpopcount,nextpermutation(), is_sorted / alpha / digit,

Compilation message

fancyfence.cpp: In function 'void solve()':
fancyfence.cpp:58:6: warning: variable 'mi' set but not used [-Wunused-but-set-variable]
   58 |  int mi[n + 1][n + 1];
      |      ^~

Subtask #1
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 12 ms 8304 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 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
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 10 ms 8280 KB Output is correct
3 Runtime error 124 ms 262144 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 8132 KB Output is correct
2 Runtime error 121 ms 262144 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 9 ms 8296 KB Output is correct
3 Runtime error 117 ms 262144 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #6
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 12 ms 8284 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 10 ms 8284 KB Output is correct
9 Correct 10 ms 8336 KB Output is correct
10 Correct 9 ms 8324 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 3 ms 2396 KB Output is correct
13 Correct 10 ms 8284 KB Output is correct
14 Correct 10 ms 8312 KB Output is correct
15 Correct 9 ms 8332 KB Output is correct
16 Correct 0 ms 348 KB Output is correct

Subtask #7
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 12 ms 8304 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 10 ms 8336 KB Output is correct
5 Correct 0 ms 348 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 1 ms 344 KB Output is correct
10 Correct 9 ms 8256 KB Output is correct
11 Runtime error 142 ms 262144 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -