Submission #64770

ソースコード

?
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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include <bits/stdc++.h>
using namespace std;
typedef long long SEGNODE_TYPE; // セグ木のノードの型の定義
class Segtree
{
public:
SEGNODE_TYPE monoid;
int segsize; // セグ木の大きさ
vector<SEGNODE_TYPE> value;
// [引数]
// int n : 大きさ
// SEGNODE_TYPE start : 初期値
// SEGNODE_TYPE mnd : 単位元（モノイド）
// [動作]
// セグ木を作る
// ※SEGNODE_TYPE の定義を忘れずに
Segtree() {}
Segtree(int n, SEGNODE_TYPE start, SEGNODE_TYPE mnd) {
segsize = 1;
while(segsize < n){
segsize = segsize * 2;
}
value = vector<SEGNODE_TYPE>(2 * segsize - 1, start);
monoid = mnd;
}
// [引数]
// int i : 変更箇所
// SEGNODE_TYPE x : 変更値
// [動作]
// 場所iをxに変更
void UpDate(int i, SEGNODE_TYPE x) {
i += segsize - 1;
value[i] = x;
while(i > 0){
i = (i-1) / 2;
value[i] = Requirement(value[i * 2 + 1], value[i * 2 + 2]);
}
return;
}
// [引数]
// int a : 区間の左端
// int b : 区間の右端
// [動作]
// 区間[a, b)のクエリを処理する（SegQueryへ橋渡し）
// ※呼び出す際にはSEGNODE_TYPE Requirement(SEGNODE_TYPE x, SEGNODE_TYPE y)の中身を確認
SEGNODE_TYPE Query(int a, int b) {
return ( SegQuery(a, b, 0, 0, segsize) );
}
// [引数]
// int a : クエリの範囲の左端
// int b : クエリの範囲の右端
// int k : 今いるノードの場所
// int l : 今いるノードの参照範囲の左端
// int r : 今いるノードの参照範囲の右端
// [動作]
// 区間[a, b)のクエリを求める
SEGNODE_TYPE SegQuery(int a, int b, int k, int l, int r) {
// [a, b)の区間に対するクエリについて、ノードk(区間[l, r)担当)が答える
if(r <= a || b <= l) {
return (monoid);
}
if(a <= l && r <= b){
// ノードkの担当クエリ区間[a ,b)に完全に含まれる
return (value[k]);
}
else {
// 左右の子に尋ねる
SEGNODE_TYPE c1 = SegQuery(a, b, 2*k+1, l, (l+r)/2); // 左の子（状況に合わせて型を変える）
SEGNODE_TYPE c2 = SegQuery(a, b, 2*k+2, (l+r)/2, r); // 右の子（状況に合わせて型を変える）
return ( Requirement(c1, c2) ); // 左右の子から求めたいものを返す
}
}
// 求めたいもの（最小値ならmin(x, y)、最大値ならmax(x, y)、合計値なら(x + y)など）
// ※ここのreturn文は用途に合わせて書き換える必要がある
SEGNODE_TYPE Requirement(SEGNODE_TYPE x, SEGNODE_TYPE y) {
return ( max(x, y) );
}
// [引数]
// int i : 場所
// [動作]
// 左からi番目の値を変えす
SEGNODE_TYPE GetReaf(int i) {
return( value[i + segsize - 1] );
}
};
signed main() {
int h, w, n;
int y, x;
long long p;
long long ans;
vector<pair<int, int> > pos;
map<pair<int, int>, long long> point;
pair<int, int> loc;
cin >> h >> w >> n;
Segtree value = Segtree(w, 0, 0);
for ( int i = 0; i < n; i++ ) {
cin >> y >> x >> p;
y--;
x--;
loc = make_pair(y, x);
pos.push_back(loc);
point[loc] = p;
}
sort(pos.begin(), pos.end());
ans = 0;
for ( int i = 0; i < n; i++ ) {
loc = pos[i];
value.UpDate(loc.second, value.Query(0, 1+loc.second)+point[loc]);
ans = max(ans, value.GetReaf(loc.second));
}
cout << ans << endl;
return (0);
}

ステータス

項目 データ
問題 1436 - Simple Grid Problem
ユーザー名 ei1903
投稿日時 2020-11-18 12:13:31
言語 C++17
状態 Accepted
得点 6
ソースコード長 4200 Byte
最大実行時間 321 ms
最大メモリ使用量 18880 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in01.txt AC 243 ms 13256 KB
1
in02.txt AC 95 ms 5072 KB
1
in03.txt AC 153 ms 9520 KB
1
in04.txt AC 235 ms 15160 KB
1
in05.txt AC 41 ms 5416 KB
1
in06.txt AC 312 ms 18712 KB
1
in07.txt AC 302 ms 18680 KB
1
in08.txt AC 321 ms 18648 KB
1
in09.txt AC 297 ms 18616 KB
1
in10.txt AC 308 ms 18708 KB
1
in11.txt AC 313 ms 18676 KB
1
in12.txt AC 312 ms 18636 KB
1
in13.txt AC 278 ms 18608 KB
1
in14.txt AC 280 ms 18572 KB
1
in15.txt AC 16 ms 4604 KB
1
in16.txt AC 20 ms 4568 KB
1
in17.txt AC 19 ms 4536 KB
1
in18.txt AC 277 ms 14604 KB
1
in19.txt AC 253 ms 14568 KB
1
in20.txt AC 267 ms 14528 KB
1
in21.txt AC 268 ms 14624 KB
1
in22.txt AC 298 ms 18812 KB
1
in23.txt AC 304 ms 18648 KB
1
in24.txt AC 292 ms 18740 KB
1
in25.txt AC 287 ms 18708 KB
1
in26.txt AC 277 ms 18804 KB
1
in27.txt AC 291 ms 18772 KB
1
in28.txt AC 295 ms 18616 KB
1
in29.txt AC 294 ms 18708 KB
1
in30.txt AC 281 ms 18800 KB
1
in31.txt AC 60 ms 7260 KB
1
in32.txt AC 225 ms 12928 KB
1
in33.txt AC 245 ms 14648 KB
1
in34.txt AC 19 ms 684 KB
1
in35.txt AC 284 ms 18812 KB
1
in36.txt AC 296 ms 18784 KB
1
in37.txt AC 296 ms 18880 KB
1
in38.txt AC 20 ms 564 KB
1
in39.txt AC 22 ms 664 KB
1
in40.txt AC 21 ms 636 KB
1
in41.txt AC 292 ms 18768 KB
1
in42.txt AC 297 ms 18864 KB
1
sample01.txt AC 22 ms 676 KB
1
sample02.txt AC 24 ms 648 KB
1