Submission #337560

#	Time	Username	Problem	Language	Result	Execution time	Memory
337560		Kerim	Divide and conquer (IZhO14_divide)	C++17	100 / 100	112 ms	16492 KiB

divide

#include "bits/stdc++.h"
#define MAXN 200009
#define INF 1000000000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
ll F[MAXN];
void upd(int x,ll val){
	for(;x<MAXN;x+=x&(-x))
		umin(F[x],val);	
}
ll tap(int x){
	ll res=INF;
	for(;x;x-=x&(-x))
		umin(res,F[x]);
	return res;
}	
int x[MAXN];
ll e[MAXN],g[MAXN];
map<ll,int>pm;
int main(){
  // freopen("file.in", "r", stdin);
    for(int i=0;i<MAXN;i++)F[i]=INF;
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
    	scanf("%d%lld%lld",x+i,g+i,e+i);
    	g[i]+=g[i-1];e[i]+=e[i-1];
    	pm[e[i-1]-x[i]]=pm[e[i]-x[i]]=1;
    }
    int c=0;
    tr(it,pm)
    	it->ss=++c;
    ll ans=0;
    for(int i=1;i<=n;i++){
    	upd(pm[e[i-1]-x[i]],g[i-1]);
		umax(ans,g[i]-tap(pm[e[i]-x[i]]));	
    }printf("%lld\n",ans);
	return 0;
}

Compilation message (stderr)

divide.cpp: In function 'int main()':
divide.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   38 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
divide.cpp:40:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   40 |      scanf("%d%lld%lld",x+i,g+i,e+i);
      |      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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