oj.uz

답안 #498496

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
498496 2021-12-25T10:29:06 Z tmn2005 금 캐기 (IZhO14_divide) C++17
100 / 100
 185 ms 17596 KB 
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

#define ar array
#define fr first
#define sc second

#define vec vector
#define ret return

#define ins insert
#define mk make_pair
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_back

#define int long long

#define pii pair<int,int>

#define all(s) s.begin(), s.end()
#define allr(s) s.rbegin(), s.rend()

#define NeedForSpeed ios::sync_with_stdio(0),cin.tie(0);
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
const int N=1e6+12,INF=1e9,mod = 1e9+7;
bool iswowel(char n){ n = toupper(n); if(n == 'A' || n == 'O' || n == 'U' || n == 'E' || n == 'I') return true; else return false;}
int n,m,k,x,y,l,r,o,ans,res,ok,mx,mn = INF;
int a[N],b[N],c[N],t[N*4];
map<int,int>dp,pr;

int get(int v,int l,int r,int x){
	if(l == r)
		ret l;
	int m = l + r >> 1;
		
	if(x < t[v*2])
		ret get(v*2+1,m+1,r,x);
		
	else
		ret get(v*2,l,m,x);
}
void build(int v,int l,int r,int i,int x){
	if(l == r)
		t[v] = x;
	else{
		int m = l + r >> 1;
		if(i <= m)
			build(v*2,l,m,i,x);
		else
			build(v*2+1,m+1,r,i,x);
		t[v] = min(t[v*2], t[v*2+1]);
	}
}
main(){
	NeedForSpeed
    cin>>n;
    for(int i=1; i<=n; i++){
    	cin>>a[i]>>b[i]>>c[i];
    	
		dp[i] = dp[i-1] + b[i];
		pr[i] = pr[i-1] + c[i];
		build(1,1,n, i,pr[i-1] - a[i]);
	}
	for(int i=1; i<=n; i++){
		int j = get(1,1,n,pr[i] - a[i]);
		res = max(res, dp[i] - dp[j-1]);
	}
	cout<<res;
	return 0;
}

Compilation message

divide.cpp: In function 'long long int get(long long int, long long int, long long int, long long int)':
divide.cpp:38:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |  int m = l + r >> 1;
      |          ~~^~~
divide.cpp: In function 'void build(long long int, long long int, long long int, long long int, long long int)':
divide.cpp:50:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |   int m = l + r >> 1;
      |           ~~^~~
divide.cpp: At global scope:
divide.cpp:58:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   58 | main(){
      | ^~~~

Subtask #1
17.0 / 17.0

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

Subtask #2
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 300 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 460 KB Output is correct
17 Correct 1 ms 460 KB Output is correct
18 Correct 1 ms 588 KB Output is correct
19 Correct 1 ms 460 KB Output is correct
20 Correct 2 ms 460 KB Output is correct
21 Correct 2 ms 580 KB Output is correct
22 Correct 2 ms 592 KB Output is correct
23 Correct 6 ms 1316 KB Output is correct
24 Correct 8 ms 1232 KB Output is correct

Subtask #3
52.0 / 52.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 300 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 460 KB Output is correct
17 Correct 1 ms 460 KB Output is correct
18 Correct 1 ms 588 KB Output is correct
19 Correct 1 ms 460 KB Output is correct
20 Correct 2 ms 460 KB Output is correct
21 Correct 2 ms 580 KB Output is correct
22 Correct 2 ms 592 KB Output is correct
23 Correct 6 ms 1316 KB Output is correct
24 Correct 8 ms 1232 KB Output is correct
25 Correct 8 ms 1156 KB Output is correct
26 Correct 12 ms 2200 KB Output is correct
27 Correct 15 ms 2264 KB Output is correct
28 Correct 76 ms 8972 KB Output is correct
29 Correct 65 ms 8896 KB Output is correct
30 Correct 185 ms 17452 KB Output is correct
31 Correct 143 ms 17468 KB Output is correct
32 Correct 146 ms 17596 KB Output is correct
33 Correct 133 ms 17388 KB Output is correct
34 Correct 139 ms 17404 KB Output is correct
35 Correct 141 ms 17416 KB Output is correct
36 Correct 149 ms 17400 KB Output is correct