제출 #1334628

#제출 시각아이디문제언어결과실행 시간메모리
1334628rexdinoFancy Fence (CEOI20_fancyfence)C++20
0 / 100
15 ms1228 KiB
#include <bits/stdc++.h>
#define fi first
#define se second
#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define REP(i,a,b) for(int i=(a); i>=(b); --i)
#define umax(x, y) x = max(x, (y))
#define umin(x, y) x = min(x, (y))
#define BIT(x, i) (((x) >> (i)) & 1)
#define MASK(i) (1LL << (i))
#define sz(v) (int)(v).size()
#define ALL(v) (v).begin(),(v).end()
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int N = 1e6 + 5;
const int mod = 1e9 + 7;
const int base = 311;
const ll INF = 1e18;

void add(int &a, int b) { a += b; if (a >= mod) a -= mod; }
int sub(int a, int b) { a -= b; if (a < 0) a += mod; return a; }
int mul(int a, int b) { return 1ll * a * b % mod; }
// Author: rexdino
int n, h[N], w[N];
int inv2, ans;

int binpow(int a, int b){
	int res = 1;
	while(b){
		if (b & 1) res = mul(res, a);
		a = mul(a, a);
		b >>= 1;
	}

	return res;
}

int C2(int n){
	return mul(mul(n, n + 1), inv2);
}

namespace sub26{
	void solve(){
		FOR(i, 1, n) FOR(j, i + 1, n){

		}
	}
}

namespace sub2{
	bool check(){
		return n <= 50;
	}
	void solve(){
		int ans = 0;
		FOR(i, 1, n){
			FOR(j, i, n){
				add(ans, min(h[i], h[j]));
			}
		}

		cout << ans;
	}
}

namespace sub3{
	bool check(){
		FOR(i, 1, n) if (h[i] != 1 && h[i] != 2) return 0;
		return 1;
	}

	void solve(){
		FOR(i, 1, n){
			if (h[i] == 2){
				int j = i;
				while(h[j + 1] == 2 && j < n) j++;

				add(ans, mul(2, C2(sub(w[j], w[i - 1]))));

				i = j;
			}
		}

		add(ans, C2(w[n]));

		cout << ans;
	}
}

namespace sub4{
	bool check(){
		FOR(i, 2, n) if (h[i] != h[i - 1]) return 0;
		return 1;
	}
	void solve(){
		ans = mul(C2(h[1]), C2(w[n]));

		cout << ans;
	}
}

namespace sub5{
	bool check(){
		FOR(i, 2, n) if (h[i] < h[i - 1]) return 0;
		return 1;
	}
	void solve(){
		FOR(i, 1, n){
			int j = i;
			while(h[j + 1] == h[i] && j < n) j++;

			int k = h[i] - h[i - 1];

			add(ans, mul(C2(k), C2(sub(w[n], w[i - 1]))));
			add(ans, mul(mul(k, h[i - 1]), C2(sub(w[n], w[i - 1]))));

			// cerr << ans << "\n";
			i = j;
		}

		cout << ans;
	}
}

void solve(){
	cin >> n;
	FOR(i, 1, n) cin >> h[i];
	FOR(i, 1, n) cin >> w[i], add(w[i], w[i - 1]);

	inv2 = binpow(2, mod - 2);

	if (sub2::check()) return sub2::solve();
	if (sub4::check()) return sub4::solve();
	if (sub3::check()) return sub3::solve();
	if (sub5::check()) return sub5::solve();
	if (n <= 1000) return sub26::solve();

}

signed main(){
    #define NAME "main"
    if (fopen(NAME".inp", "r")){
        freopen(NAME".inp", "r", stdin);
        freopen(NAME".out", "w", stdout);
    }
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int t = 1;
    // cin >> t;
    while(t--) solve();

    // cerr << "Time elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << "s\n";
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

fancyfence.cpp: In function 'int main()':
fancyfence.cpp:146:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  146 |         freopen(NAME".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fancyfence.cpp:147:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  147 |         freopen(NAME".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...