Submission #581911

#	Time	Username	Problem	Language	Result	Execution time	Memory
581911		Mr_Husanboy	Divide and conquer (IZhO14_divide)	C++14	48 / 100	1074 ms	2376 KiB

divide

// 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),e(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; e[i]=e[i-1]+c;
	} ll ans=0;
	for(int i=i;i<=n;i++){
		for(int j=i;j<=n;j++){
			if(e[j]-e[i-1]>=x[j]-x[i]){
				ans=max(g[j]-g[i-1],ans);
			}
		}
	}
	cout<<ans;
}
 
int main(){
	ios;
//	int t; cin>>t; while(t--)
	solve();
}

Compilation message (stderr)

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++){
      |                ~^~~~~~~~~~~~
divide.cpp: In function 'void solve()':
divide.cpp:50:10: warning: 'i' may be used uninitialized in this function [-Wmaybe-uninitialized]
   50 |  for(int i=i;i<=n;i++){
      |          ^

• Subtask 1: 17 / 17
• Subtask 2: 31 / 31
• Subtask 3: 0 / 52