// Muallif: Mansuraliyev Husanboy Murotali o'g'li >> NamPS
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ios ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define all(a) a.begin(), a.end()
#define F first
#define S second
#define fp(a,i,c) for(int (a) = (i); (a) < (c); (a)++)
#define fm(a,i,c) for(int (a) = (i); (a) >= (c); (a)--)
#define vii vector<int>
#define vll vector<ll>
// 0-9 >> 48-57; A-Z>>65-90 and a-z>>97-122 respectively;
const ll mod=1e9+7;
vector<vll> matrix_mult(vector<vll> a, vector<vll> b){
if(a[0].size()!=b.size()){
cout<<"Fake!\n";return {{-1}};
}vector<vll> res(a.size(),vll(b.size()));
for(int i=0;i<a.size();i++){
for(int j=0;j<b.size();j++){
ll num=0;
for(int k=0;k<a[0].size();k++){
num+=a[i][k]*b[k][j];
num%=mod;
}
res[i][j]=num;
}
}
return res;
}
void solve(){
int n; cin>>n;
vector<ll> x(n+1),g(n+1),en(n+1);
for(int i=1;i<=n;i++){
ll a,b,c; cin>>a>>b>>c;
x[i]=a; g[i]=g[i-1]+b,en[i]=en[i-1]+c;
}
vector<ll> dif(n+1); map<ll,int>mp;
multiset<ll> st;
for(int i=1;i<=n;i++){
x[i]-=x[1];
dif[i]=en[i]-x[i];
st.insert(dif[i]);
mp[dif[i]]=max(i,mp[dif[i]]);
}ll ans=0;
for(int i=1;i<=n;i++){
auto it=st.lower_bound(en[i-1]-x[i]);
ans=max(ans,g[mp[*it]]-g[i-1]);
st.erase(st.find(dif[i]));
// cout<<ans<<endl;
}
cout<<ans;
}
int main(){
ios;
// int t; cin>>t; while(t--)
solve();
}
Compilation message
divide.cpp: In function 'std::vector<std::vector<long long int> > matrix_mult(std::vector<std::vector<long long int> >, std::vector<std::vector<long long int> >)':
divide.cpp:24:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | for(int i=0;i<a.size();i++){
| ~^~~~~~~~~
divide.cpp:25:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | for(int j=0;j<b.size();j++){
| ~^~~~~~~~~
divide.cpp:27:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
27 | for(int k=0;k<a[0].size();k++){
| ~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
