oj.uz

Submission #166390

# Submission time Handle Problem Language Result Execution time Memory
166390 2019-12-02T03:59:34 Z abil Divide and conquer (IZhO14_divide) C++14
100 / 100
 73 ms 9064 KB 
#include <bits/stdc++.h>
 
#define fr first
#define sc second
#define pb push_back
#define mk make_pair
#define all(s) s.begin(),s.end()
#define int long long
 
using namespace std;
 
const int N = (1e6 + 12);
const int mod = (1e9 + 7);
const int INF = (1e15 + 9);
 
int x[N], g[N], c[N], pr[N], prg[N], mx[N];
vector<pair<int,int > > vec;
main()
{
	int n;
	scanf("%lld", &n);
	for(int i = 1;i <= n; i++){
		scanf("%lld%lld%lld", &x[i], &g[i], &c[i]);
		pr[i] = pr[i - 1] + c[i];
		vec.pb({x[i] - pr[i], i});
		prg[i] = prg[i - 1] + g[i];
	}
	sort(all(vec));
	for(int i = 0;i < vec.size(); i++){
		mx[i] = max(vec[i].sc, mx[i - 1]);
	}
	int ans = 0;
	for(int i = 1;i <= n; i++){
		int pos = upper_bound(all(vec), make_pair(x[i] - pr[i - 1], INF)) - vec.begin();
		ans = max(ans, prg[mx[pos - 1]] - prg[i - 1]);
	}
	cout << ans;
}

Compilation message

divide.cpp:18:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
divide.cpp: In function 'int main()':
divide.cpp:29:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;i < vec.size(); i++){
                ~~^~~~~~~~~~~~
divide.cpp:21:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &n);
  ~~~~~^~~~~~~~~~~~
divide.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld", &x[i], &g[i], &c[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 2 ms 248 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 3 ms 504 KB Output is correct
10 Correct 3 ms 524 KB Output is correct
11 Correct 5 ms 888 KB Output is correct
12 Correct 5 ms 760 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 760 KB Output is correct
2 Correct 6 ms 1144 KB Output is correct
3 Correct 7 ms 1116 KB Output is correct
4 Correct 27 ms 3660 KB Output is correct
5 Correct 31 ms 3692 KB Output is correct
6 Correct 68 ms 6772 KB Output is correct
7 Correct 50 ms 6756 KB Output is correct
8 Correct 50 ms 6892 KB Output is correct
9 Correct 73 ms 6876 KB Output is correct
10 Correct 51 ms 6728 KB Output is correct
11 Correct 56 ms 8904 KB Output is correct
12 Correct 59 ms 9064 KB Output is correct