import java.util.*;
import java.io.*;
public class art {
public static void main(String[] args) throws IOException{
BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(new PrintStream(System.out));
int n=Integer.parseInt(f.readLine());
long ans=0;
pair[]arr=new pair[n];
for(int i=0;i<n;i++){
StringTokenizer st=new StringTokenizer(f.readLine());
long a=Long.parseLong(st.nextToken());
long b=Long.parseLong(st.nextToken());
ans=Math.max(ans,b);
arr[i]=new pair(a,b);
}
Arrays.sort(arr);
long best=0;
long pfx=0;
long lastpfx=0;
for(int i=0;i<n;i++){
pfx+=arr[i].val;
ans=Math.max(pfx-arr[i].size+best,ans);
best=Math.max(best,-lastpfx+arr[i].size);
lastpfx=pfx;
}
System.out.print(ans);
f.close();
out.close();
}
}class pair implements Comparable <pair>{
long size;
long val;
public int compareTo(pair other){
if(size>other.size)return 1;
return -1;
}
pair(long a, long b)
{
size=a;
val=b;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
92 ms |
9792 KB |
Output is correct |
2 |
Correct |
91 ms |
9832 KB |
Output is correct |
3 |
Correct |
94 ms |
9840 KB |
Output is correct |
4 |
Correct |
89 ms |
9888 KB |
Output is correct |
5 |
Correct |
91 ms |
9608 KB |
Output is correct |
6 |
Correct |
91 ms |
9844 KB |
Output is correct |
7 |
Correct |
90 ms |
9668 KB |
Output is correct |
8 |
Correct |
94 ms |
9788 KB |
Output is correct |
9 |
Correct |
89 ms |
9704 KB |
Output is correct |
10 |
Correct |
93 ms |
9660 KB |
Output is correct |
11 |
Correct |
91 ms |
9660 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
92 ms |
9792 KB |
Output is correct |
2 |
Correct |
91 ms |
9832 KB |
Output is correct |
3 |
Correct |
94 ms |
9840 KB |
Output is correct |
4 |
Correct |
89 ms |
9888 KB |
Output is correct |
5 |
Correct |
91 ms |
9608 KB |
Output is correct |
6 |
Correct |
91 ms |
9844 KB |
Output is correct |
7 |
Correct |
90 ms |
9668 KB |
Output is correct |
8 |
Correct |
94 ms |
9788 KB |
Output is correct |
9 |
Correct |
89 ms |
9704 KB |
Output is correct |
10 |
Correct |
93 ms |
9660 KB |
Output is correct |
11 |
Correct |
91 ms |
9660 KB |
Output is correct |
12 |
Correct |
114 ms |
10872 KB |
Output is correct |
13 |
Correct |
106 ms |
10320 KB |
Output is correct |
14 |
Correct |
101 ms |
10068 KB |
Output is correct |
15 |
Correct |
107 ms |
10652 KB |
Output is correct |
16 |
Correct |
130 ms |
10404 KB |
Output is correct |
17 |
Correct |
120 ms |
10280 KB |
Output is correct |
18 |
Correct |
106 ms |
10236 KB |
Output is correct |
19 |
Correct |
109 ms |
10068 KB |
Output is correct |
20 |
Correct |
113 ms |
10828 KB |
Output is correct |
21 |
Correct |
105 ms |
10212 KB |
Output is correct |
22 |
Correct |
108 ms |
10856 KB |
Output is correct |
23 |
Correct |
106 ms |
10484 KB |
Output is correct |
24 |
Correct |
106 ms |
10788 KB |
Output is correct |
25 |
Correct |
106 ms |
10500 KB |
Output is correct |
26 |
Correct |
107 ms |
10376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
92 ms |
9792 KB |
Output is correct |
2 |
Correct |
91 ms |
9832 KB |
Output is correct |
3 |
Correct |
94 ms |
9840 KB |
Output is correct |
4 |
Correct |
89 ms |
9888 KB |
Output is correct |
5 |
Correct |
91 ms |
9608 KB |
Output is correct |
6 |
Correct |
91 ms |
9844 KB |
Output is correct |
7 |
Correct |
90 ms |
9668 KB |
Output is correct |
8 |
Correct |
94 ms |
9788 KB |
Output is correct |
9 |
Correct |
89 ms |
9704 KB |
Output is correct |
10 |
Correct |
93 ms |
9660 KB |
Output is correct |
11 |
Correct |
91 ms |
9660 KB |
Output is correct |
12 |
Correct |
114 ms |
10872 KB |
Output is correct |
13 |
Correct |
106 ms |
10320 KB |
Output is correct |
14 |
Correct |
101 ms |
10068 KB |
Output is correct |
15 |
Correct |
107 ms |
10652 KB |
Output is correct |
16 |
Correct |
130 ms |
10404 KB |
Output is correct |
17 |
Correct |
120 ms |
10280 KB |
Output is correct |
18 |
Correct |
106 ms |
10236 KB |
Output is correct |
19 |
Correct |
109 ms |
10068 KB |
Output is correct |
20 |
Correct |
113 ms |
10828 KB |
Output is correct |
21 |
Correct |
105 ms |
10212 KB |
Output is correct |
22 |
Correct |
108 ms |
10856 KB |
Output is correct |
23 |
Correct |
106 ms |
10484 KB |
Output is correct |
24 |
Correct |
106 ms |
10788 KB |
Output is correct |
25 |
Correct |
106 ms |
10500 KB |
Output is correct |
26 |
Correct |
107 ms |
10376 KB |
Output is correct |
27 |
Correct |
197 ms |
15252 KB |
Output is correct |
28 |
Correct |
208 ms |
16480 KB |
Output is correct |
29 |
Correct |
198 ms |
15496 KB |
Output is correct |
30 |
Correct |
189 ms |
15288 KB |
Output is correct |
31 |
Correct |
186 ms |
15292 KB |
Output is correct |
32 |
Correct |
187 ms |
15096 KB |
Output is correct |
33 |
Correct |
191 ms |
15224 KB |
Output is correct |
34 |
Correct |
224 ms |
13580 KB |
Output is correct |
35 |
Correct |
194 ms |
14852 KB |
Output is correct |
36 |
Correct |
196 ms |
15344 KB |
Output is correct |
37 |
Correct |
185 ms |
15104 KB |
Output is correct |
38 |
Correct |
182 ms |
15140 KB |
Output is correct |
39 |
Correct |
184 ms |
15096 KB |
Output is correct |
40 |
Correct |
190 ms |
15072 KB |
Output is correct |
41 |
Correct |
186 ms |
15248 KB |
Output is correct |
42 |
Correct |
234 ms |
15760 KB |
Output is correct |
43 |
Correct |
197 ms |
15724 KB |
Output is correct |
44 |
Correct |
181 ms |
15408 KB |
Output is correct |
45 |
Correct |
197 ms |
15568 KB |
Output is correct |
46 |
Correct |
235 ms |
13872 KB |
Output is correct |
47 |
Correct |
199 ms |
15656 KB |
Output is correct |
48 |
Correct |
192 ms |
15232 KB |
Output is correct |
49 |
Correct |
189 ms |
15308 KB |
Output is correct |
50 |
Correct |
193 ms |
15224 KB |
Output is correct |
51 |
Correct |
196 ms |
15428 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
92 ms |
9792 KB |
Output is correct |
2 |
Correct |
91 ms |
9832 KB |
Output is correct |
3 |
Correct |
94 ms |
9840 KB |
Output is correct |
4 |
Correct |
89 ms |
9888 KB |
Output is correct |
5 |
Correct |
91 ms |
9608 KB |
Output is correct |
6 |
Correct |
91 ms |
9844 KB |
Output is correct |
7 |
Correct |
90 ms |
9668 KB |
Output is correct |
8 |
Correct |
94 ms |
9788 KB |
Output is correct |
9 |
Correct |
89 ms |
9704 KB |
Output is correct |
10 |
Correct |
93 ms |
9660 KB |
Output is correct |
11 |
Correct |
91 ms |
9660 KB |
Output is correct |
12 |
Correct |
114 ms |
10872 KB |
Output is correct |
13 |
Correct |
106 ms |
10320 KB |
Output is correct |
14 |
Correct |
101 ms |
10068 KB |
Output is correct |
15 |
Correct |
107 ms |
10652 KB |
Output is correct |
16 |
Correct |
130 ms |
10404 KB |
Output is correct |
17 |
Correct |
120 ms |
10280 KB |
Output is correct |
18 |
Correct |
106 ms |
10236 KB |
Output is correct |
19 |
Correct |
109 ms |
10068 KB |
Output is correct |
20 |
Correct |
113 ms |
10828 KB |
Output is correct |
21 |
Correct |
105 ms |
10212 KB |
Output is correct |
22 |
Correct |
108 ms |
10856 KB |
Output is correct |
23 |
Correct |
106 ms |
10484 KB |
Output is correct |
24 |
Correct |
106 ms |
10788 KB |
Output is correct |
25 |
Correct |
106 ms |
10500 KB |
Output is correct |
26 |
Correct |
107 ms |
10376 KB |
Output is correct |
27 |
Correct |
197 ms |
15252 KB |
Output is correct |
28 |
Correct |
208 ms |
16480 KB |
Output is correct |
29 |
Correct |
198 ms |
15496 KB |
Output is correct |
30 |
Correct |
189 ms |
15288 KB |
Output is correct |
31 |
Correct |
186 ms |
15292 KB |
Output is correct |
32 |
Correct |
187 ms |
15096 KB |
Output is correct |
33 |
Correct |
191 ms |
15224 KB |
Output is correct |
34 |
Correct |
224 ms |
13580 KB |
Output is correct |
35 |
Correct |
194 ms |
14852 KB |
Output is correct |
36 |
Correct |
196 ms |
15344 KB |
Output is correct |
37 |
Correct |
185 ms |
15104 KB |
Output is correct |
38 |
Correct |
182 ms |
15140 KB |
Output is correct |
39 |
Correct |
184 ms |
15096 KB |
Output is correct |
40 |
Correct |
190 ms |
15072 KB |
Output is correct |
41 |
Correct |
186 ms |
15248 KB |
Output is correct |
42 |
Correct |
234 ms |
15760 KB |
Output is correct |
43 |
Correct |
197 ms |
15724 KB |
Output is correct |
44 |
Correct |
181 ms |
15408 KB |
Output is correct |
45 |
Correct |
197 ms |
15568 KB |
Output is correct |
46 |
Correct |
235 ms |
13872 KB |
Output is correct |
47 |
Correct |
199 ms |
15656 KB |
Output is correct |
48 |
Correct |
192 ms |
15232 KB |
Output is correct |
49 |
Correct |
189 ms |
15308 KB |
Output is correct |
50 |
Correct |
193 ms |
15224 KB |
Output is correct |
51 |
Correct |
196 ms |
15428 KB |
Output is correct |
52 |
Execution timed out |
1097 ms |
115264 KB |
Time limit exceeded |
53 |
Halted |
0 ms |
0 KB |
- |