oj.uz

Submission #1040368

# Submission time Handle Problem Language Result Execution time Memory
1040368 2024-08-01T02:31:30 Z vjudge1 Divide and conquer (IZhO14_divide) C++14
0 / 100
 0 ms 348 KB 
#include <bits/stdc++.h>
using namespace std;

int main()
{
	int n;
	cin >> n;
	long long a[n+1],b[n+1],c[n+1],d[n+1],f[n+1],g[n+1];
	for(int i=0;i<n;i++)
	{
	    cin >> a[i+1] >> b[i+1] >> c[i+1];
	}
	a[0]=0;b[0]=0;c[0]=a[1]-a[0];d[0]=c[0];g[0]=0;f[0]=c[0];
	for(int i=1;i<=n;i++)
	{
	    g[i]=g[i-1]+b[i];
	    d[i]=c[i]+d[i-1];
	    f[i]=d[i]-a[i];
	}
	vector<pair<long long,int> > v;
	for(int i=0;i<=n;i++)
	{
	    v.push_back({f[i],i});
	}
	sort(v.begin(),v.end());
	int mn=100000000;
	long long res=0;
	for(int i=0;i<=n;i++)
	{
	    mn=min(mn,v[i].second);
	    res=max(res,g[v[i].second]-g[max(mn-1,0)]);
	}
	cout << res;
	return 0;
}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -