oj.uz

답안 #792421

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
792421 2023-07-25T04:40:13 Z GEN 이지후(#10086) Real Mountains (CCO23_day1problem2) C++17
0 / 25
 0 ms 212 KB 
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = array<int, 2>;
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using llf = long double;
const int mod = 1e6 + 3; // 1e9 + 7;//993244853;

// I don't remember the credit of modint, but it's not mine.
// I don't remember the credit of FFT, but it's probably mine.
// Polynomial library is due to adamant:
// https://github.com/cp-algorithms/cp-algorithms-aux/blob/master/src/polynomial.cpp
// To use polynomial sqrt, need to amend sqrt for modint.

struct mint {
	int val;
	mint() { val = 0; }
	mint(const lint &v) {
		val = (-mod <= v && v < mod) ? v : v % mod;
		if (val < 0)
			val += mod;
	}

	friend ostream &operator<<(ostream &os, const mint &a) { return os << a.val; }
	friend bool operator==(const mint &a, const mint &b) { return a.val == b.val; }
	friend bool operator!=(const mint &a, const mint &b) { return !(a == b); }
	friend bool operator<(const mint &a, const mint &b) { return a.val < b.val; }

	mint operator-() const { return mint(-val); }
	mint &operator+=(const mint &m) {
		if ((val += m.val) >= mod)
			val -= mod;
		return *this;
	}
	mint &operator-=(const mint &m) {
		if ((val -= m.val) < 0)
			val += mod;
		return *this;
	}
	mint &operator*=(const mint &m) {
		val = (lint)val * m.val % mod;
		return *this;
	}
	friend mint ipow(mint a, lint p) {
		mint ans = 1;
		for (; p; p /= 2, a *= a)
			if (p & 1)
				ans *= a;
		return ans;
	}
	mint inv() const { return ipow(*this, mod - 2); }
	mint &operator/=(const mint &m) { return (*this) *= m.inv(); }

	friend mint operator+(mint a, const mint &b) { return a += b; }
	friend mint operator-(mint a, const mint &b) { return a -= b; }
	friend mint operator*(mint a, const mint &b) { return a *= b; }
	friend mint operator/(mint a, const mint &b) { return a /= b; }
	operator int64_t() const { return val; }
};

mint bino(int n, int k) {
	mint up = 1, dn = 1;
	for (int i = 0; i < k; i++) {
		up *= mint(n - i);
		dn *= mint(i + 1);
	}
	return up / dn;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	lint tot = 0;
	for (int i = 1; i < 100; i++) {
		int l = 0, r = n;
		while (l < n && a[l] <= i)
			l++;
		while (r > l && a[r - 1] <= i)
			r--;
		vector<int> pos;
		vector<pi> mswp;
		int mx = 1e9;
		for (int j = l; j < r; j++) {
			if (a[j] <= i) {
				pos.push_back(j);
				mswp.push_back({mx, 0});
			} else
				mx = min(mx, a[j]);
		}
		if (sz(pos) == 0)
			continue;
		int ptr = sz(pos);
		mx = 1e9;
		for (int j = r - 1; j >= l; j--) {
			if (a[j] <= i) {
				pos.push_back(j);
				mswp[--ptr][1] = mx;
			} else
				mx = min(mx, a[j]);
		}
		vector<int> lsave(sz(pos)), rsave(sz(pos));
		for (int j = 0; j < sz(pos); j++) {
			tot += mswp[j][0] + mswp[j][1] + i;
			lsave[j] = mswp[j][1] - i;
			rsave[j] = mswp[j][0] - i;
		}
		lint run = accumulate(all(rsave), 0ll);
		lint save = 0;
		for (int j = 0; j < sz(pos); j++) {
			run -= rsave[j];
			save = max(save, run);
			run += lsave[j];
		}
		tot -= save;
	}
	cout << tot % 1000003 << "\n";
}

Subtask #1
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -