Submission #66399

ソースコード

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <bits/extc++.h>
using namespace std;
int updiv(int a, int b){
return ((a + b - 1) / b);
}
int main(){
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
int n, m, h, r;
cin >> n >> m >> h >> r;
vector<int> s(r), f(r), c(r);
for(int i = 0; i < r; ++i){
cin >> s[i] >> f[i] >> c[i];
--s[i];
}
vector<pair<int, int> > sec;
int l = 0;
for(int i = 0; i < r; ++i){
if(l < s[i]){
sec.emplace_back(s[i] - l, m);
}
sec.emplace_back(f[i] - s[i], c[i]);
l = f[i];
}
if(l != n){
sec.emplace_back(n - l, m);
}
auto rsec = sec;
reverse(rsec.begin(), rsec.end());
sec.insert(sec.begin(), {0, 0});
rsec.insert(rsec.begin(), {0, 0});
int siz = sec.size();
vector<long long> cumv(siz), rcumv(siz);
vector<int> cuml(siz), rcuml(siz);
for(int i = 1; i < siz; ++i){
cumv[i] = cumv[i - 1] + (long long) sec[i].first * sec[i].second;
cuml[i] = cuml[i - 1] + sec[i].first;
rcumv[i] = rcumv[i - 1] + (long long) rsec[i].first * rsec[i].second;
rcuml[i] = rcuml[i - 1] + rsec[i].first;
}
auto solve = [&](auto &cv, auto &cl, auto &sc){
int res = INT_MAX;
for(int i = 1; i < siz; ++i){
int low = i - 1, high = siz;
while(high - low > 1){
int mid = (high + low) / 2;
if(cv[mid] - cv[i - 1] >= h){
high = mid;
}else{
low = mid;
}
}
if(high != siz){
res = min(res, cl[high - 1] - cl[i - 1] + updiv(h - (cv[high - 1] - cv[i - 1]), sc[high].second));
}
}
return (res);
};
cout << min(solve(cumv, cuml, sec), solve(rcumv, rcuml, rsec)) << '\n';
return (0);
}

ステータス

項目 データ
問題 1493 - Sand of Star
ユーザー名 syoribu
投稿日時 2021-05-03 21:14:37
言語 C++17
状態 Accepted
得点 500
ソースコード長 1945 Byte
最大実行時間 73 ms
最大メモリ使用量 10064 KB

セット

セット 得点 Cases
1 ALL 500 / 500 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
hand_made01.txt AC 33 ms 604 KB
1
hand_made02.txt AC 22 ms 688 KB
1
hand_made03.txt AC 73 ms 9684 KB
1
hand_made04.txt AC 21 ms 516 KB
1
hand_made05.txt AC 22 ms 600 KB
1
in01.txt AC 47 ms 5568 KB
1
in02.txt AC 53 ms 8864 KB
1
in03.txt AC 34 ms 4088 KB
1
in04.txt AC 65 ms 8672 KB
1
in05.txt AC 42 ms 4000 KB
1
in06.txt AC 45 ms 4612 KB
1
in07.txt AC 41 ms 4728 KB
1
in08.txt AC 59 ms 10064 KB
1
in09.txt AC 33 ms 2940 KB
1
in10.txt AC 57 ms 6544 KB
1
in11.txt AC 28 ms 940 KB
1
in12.txt AC 25 ms 1896 KB
1
in13.txt AC 42 ms 3456 KB
1
in14.txt AC 61 ms 8480 KB
1
in15.txt AC 55 ms 7120 KB
1
in16.txt AC 33 ms 2884 KB
1
in17.txt AC 42 ms 5656 KB
1
in18.txt AC 57 ms 7216 KB
1
in19.txt AC 31 ms 1524 KB
1
in20.txt AC 49 ms 6200 KB
1
in21.txt AC 35 ms 3144 KB
1
in22.txt AC 63 ms 9820 KB
1
in23.txt AC 25 ms 1580 KB
1
in24.txt AC 49 ms 4600 KB
1
in25.txt AC 34 ms 4068 KB
1
in26.txt AC 53 ms 6876 KB
1
in27.txt AC 58 ms 7536 KB
1
in28.txt AC 36 ms 2728 KB
1
in29.txt AC 53 ms 6552 KB
1
in30.txt AC 55 ms 7432 KB
1
sample01.txt AC 27 ms 672 KB
1
sample02.txt AC 23 ms 752 KB
1