結果
| 問題 | No.703 ゴミ拾い Easy |
| ユーザー |
 legosuke
|
| 提出日時 | 2019-09-29 22:40:52 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 115 ms / 1,500 ms |
| コード長 | 5,615 bytes |
| コンパイル時間 | 1,955 ms |
| コンパイル使用メモリ | 168,852 KB |
| 実行使用メモリ | 33,152 KB |
| 最終ジャッジ日時 | 2025-01-02 14:20:48 |
| 合計ジャッジ時間 | 6,738 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 46 |
コンパイルメッセージ
main.cpp: In function ‘int main(int, char**)’:
main.cpp:162:20: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
162 | freopen("input.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:164:20: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
164 | freopen("output.txt", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
ソースコード
#include <bits/stdc++.h>
#define int long long
#define lint long long
#define pii pair<int,int>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(c) (c).begin(),(c).end()
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define MINF(a) memset(a,0x3f,sizeof(a))
#define POW(n) (1LL<<(n))
#define POPCNT(n) (__builtin_popcount(n))
#define IN(i,a,b) (a <= i && i <= b)
using namespace std;
template <typename T> inline bool CHMIN(T& a,T b) { if(a>b) { a=b; return 1; } return 0; }
template <typename T> inline bool CHMAX(T& a,T b) { if(a<b) { a=b; return 1; } return 0; }
template <typename T> inline void SORT(T& a) { sort(ALL(a)); }
template <typename T> inline void REV(T& a) { reverse(ALL(a)); }
template <typename T> inline void UNI(T& a) { sort(ALL(a)); a.erase(unique(ALL(a)),a.end()); }
template <typename T> inline T LB(vector<T>& v, T a) { return *lower_bound(ALL(v),a); }
template <typename T> inline int LBP(vector<T>& v, T a) { return lower_bound(ALL(v),a) - v.begin(); }
template <typename T> inline T UB(vector<T>& v, T a) { return *upper_bound(ALL(v),a); }
template <typename T> inline int UBP(vector<T>& v, T a) { return upper_bound(ALL(v),a) - v.begin(); }
template <typename T1, typename T2> ostream& operator<< (ostream& os, const pair<T1,T2>& p) { os << p.first << " " << p.second; return os; }
template <typename T1, typename T2> istream& operator>> (istream& is, pair<T1,T2>& p) { is >> p.first >> p.second; return is; }
template <typename T> ostream& operator<< (ostream& os, const vector<T>& v) { REP(i,v.size()) { if (i) os << " "; os << v[i]; } return os; }
template <typename T> istream& operator>> (istream& is, vector<T>& v) { for(T& in : v) is >> in; return is; }
template <typename T = int> vector<T> make_v(size_t a) { return vector<T>(a); }
template <typename T, typename... Ts> auto make_v(size_t a, Ts... ts) { return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...)); }
template <typename T, typename V> typename enable_if<is_class<T>::value == 0>::type fill_v(T &t, const V &v) { t = v; }
template <typename T, typename V> typename enable_if<is_class<T>::value != 0>::type fill_v(T &t, const V &v) { for(auto &e : t) fill_v(e,v); }
const lint MOD = 1000000007;
// const lint INF = 0x3f3f3f3f3f3f3f3f;
const double EPS = 1e-10;
const int INF = 1LL << 40;
struct LiChaoTree {
int n;
vector<int> xs; // 座標
vector<int> ps; // 直線の傾き
vector<int> qs; // 直線の切片
LiChaoTree(vector<int> &xin)
{
for (n = 1; n < xin.size(); n <<= 1);
ps.assign(n << 1, 0);
qs.assign(n << 1, INF);
xs.resize(n, INF);
for (int i = 0; i < xin.size(); ++i) {
xs[i] = xin[i];
}
}
int f(int p, int q, int x)
{
return p * x + q;
}
// 追加処理
// [l, r)
void add(int p, int q, int k, int l, int r) {
int m = (l + r) / 2;
if (ps[k] == 0 && qs[k] == INF) {
ps[k] = p;
qs[k] = q;
return;
}
bool left = (f(p, q, xs[l]) < f(ps[k], qs[k], xs[l]));
bool mid = (f(p, q, xs[m]) < f(ps[k], qs[k], xs[m]));
bool right = (f(p, q, xs[r - 1]) < f(ps[k], qs[k], xs[r - 1]));
if (left && right) {
ps[k] = p;
qs[k] = q;
return;
}
if (!left && !right)
return;
if (mid) {
swap(ps[k], p);
swap(qs[k], q);
}
if (left != mid) {
add(p, q, (k << 1) | 0, l, m);
} else {
add(p, q, (k << 1) | 1, m, r);
}
}
// 直線追加
// O(log n)
void add(int p, int q) {
return add(p, q, 1, 0, n);
}
// 線分追加 [a, b)
void add(int p, int q, int a, int b) {
int L = a + n, R = b + n;
int a0 = a, b0 = b;
int sz = 1;
while (L < R) {
if (L & 1) {
add(p, q, L, a0, a0 + sz);
L++;
a0 += sz;
}
if (R & 1) {
R--;
b0 -= sz;
add(p, q, R, b0, b0 + sz);
}
L >>= 1; R >>= 1;
sz <<= 1;
}
}
// k番目の座標の最小値 (0-indexed)
// O(log n)
int query(int k) {
int x = xs[k];
k += n;
int res = INF;
while (k > 0) {
res = min(res, f(ps[k], qs[k], x));
k >>= 1;
}
return res;
}
void print()
{
int lev = 0;
while ((1 << lev) < n) lev++;
cout << "(傾き, 切片):" << endl;
for (int i = 0; i <= lev; ++i) {
for (int j = 0; j < (1 << i); ++j) {
cout << " (" << ps[(1 << i) + j] << ", " << qs[(1 << i) + j] << ")";
}
cout << endl;
}
cout << endl;
}
};
void _main() {
int n;
cin >> n;
vector<int> a(n), x(n), y(n);
cin >> a >> x >> y;
LiChaoTree lct(a);
vector<int> dp(n + 1, 0);
for (int i = 0; i < n; ++i) {
lct.add(-2 * x[i], x[i] * x[i] + y[i] * y[i] + dp[i]);
dp[i + 1] = lct.query(i) + a[i] * a[i];
}
cout << dp[n] << endl;
}
signed main(signed argc, char **argv) {
if (argc > 1) {
if (strchr(argv[1], 'i'))
freopen("input.txt", "r", stdin);
if (strchr(argv[1], 'o'))
freopen("output.txt", "w", stdout);
}
cin.tie(nullptr);
ios::sync_with_stdio(false);
cout << fixed << setprecision(10);
_main();
return 0;
}