답안 #488699

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
488699	2021-11-20T06:11:58 Z	SirCovidThe19th	금 캐기 (IZhO14_divide)	C++17	17 / 100	3 ms	2384 KB

divide

#include <bits/stdc++.h>
using namespace std;

const int mx = 1e5 + 5, msz = (1 << 17);

int n, X[mx]; long long G[mx], E[mx], seg[msz * 2], ans; 

void upd(int i, int v){
    seg[i += msz] = v;
    for (i /= 2; i; i /= 2) seg[i] = min(seg[i * 2], seg[i * 2 + 1]); 
}
int qry(int v){
    int i = 1; 
    while (i < msz) i = (seg[i * 2] <= v) ? i * 2 : i * 2 + 1;
    return i - msz;
}

int main(){
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> X[i] >> G[i] >> E[i]; 
        G[i] += G[i - 1]; E[i] += E[i - 1];
    }
    memset(seg, 0x3f, sizeof(seg)); 
    for (int i = 1; i <= n; i++){
        upd(i, E[i - 1] - X[i]);
        int pos = qry(E[i] - X[i]);
        ans = max(ans, G[i] - G[pos - 1]);
    }
    cout<<ans<<endl;
}

Subtask #1

17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2252 KB	Output is correct
2	Correct	1 ms	2252 KB	Output is correct
3	Correct	1 ms	2252 KB	Output is correct
4	Correct	1 ms	2252 KB	Output is correct
5	Correct	1 ms	2252 KB	Output is correct
6	Correct	1 ms	2328 KB	Output is correct
7	Correct	1 ms	2252 KB	Output is correct
8	Correct	1 ms	2252 KB	Output is correct
9	Correct	1 ms	2252 KB	Output is correct
10	Correct	1 ms	2252 KB	Output is correct
11	Correct	2 ms	2252 KB	Output is correct
12	Correct	1 ms	2252 KB	Output is correct

Subtask #2

0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2252 KB	Output is correct
2	Correct	1 ms	2252 KB	Output is correct
3	Correct	1 ms	2252 KB	Output is correct
4	Correct	1 ms	2252 KB	Output is correct
5	Correct	1 ms	2252 KB	Output is correct
6	Correct	1 ms	2328 KB	Output is correct
7	Correct	1 ms	2252 KB	Output is correct
8	Correct	1 ms	2252 KB	Output is correct
9	Correct	1 ms	2252 KB	Output is correct
10	Correct	1 ms	2252 KB	Output is correct
11	Correct	2 ms	2252 KB	Output is correct
12	Correct	1 ms	2252 KB	Output is correct
13	Correct	1 ms	2252 KB	Output is correct
14	Correct	2 ms	2252 KB	Output is correct
15	Correct	1 ms	2252 KB	Output is correct
16	Correct	2 ms	2252 KB	Output is correct
17	Correct	2 ms	2372 KB	Output is correct
18	Incorrect	3 ms	2384 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #3

0 / 52.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2252 KB	Output is correct
2	Correct	1 ms	2252 KB	Output is correct
3	Correct	1 ms	2252 KB	Output is correct
4	Correct	1 ms	2252 KB	Output is correct
5	Correct	1 ms	2252 KB	Output is correct
6	Correct	1 ms	2328 KB	Output is correct
7	Correct	1 ms	2252 KB	Output is correct
8	Correct	1 ms	2252 KB	Output is correct
9	Correct	1 ms	2252 KB	Output is correct
10	Correct	1 ms	2252 KB	Output is correct
11	Correct	2 ms	2252 KB	Output is correct
12	Correct	1 ms	2252 KB	Output is correct
13	Correct	1 ms	2252 KB	Output is correct
14	Correct	2 ms	2252 KB	Output is correct
15	Correct	1 ms	2252 KB	Output is correct
16	Correct	2 ms	2252 KB	Output is correct
17	Correct	2 ms	2372 KB	Output is correct
18	Incorrect	3 ms	2384 KB	Output isn't correct
19	Halted	0 ms	0 KB	-