Submission #425612

#	Time	Username	Problem	Language	Result	Execution time	Memory
425612		haojiandan	Shortcut (IOI16_shortcut)	C++14	38 / 100	2088 ms	220840 KiB

shortcut

#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e16;
const int maxn=(1e6)+10;
int n,c;
ll s[maxn],d[maxn];
ll m1[3010][3010],m2[3010][3010],m3[3010][3010],m4[3010][3010];
vector<ll> D;
void update(ll &x,ll &y) { if (x<y) x=y; }
ll cmax(ll x,ll y) { if (x>y) return x; return y; }
ll solve(ll M) {
	for (int i=1;i<=n;i++) for (int j=i+1;j<=n;j++) {
		if (s[j]-s[i]+d[i]+d[j]>M) {
			m1[i][j]=s[i]+s[j]+d[i]+d[j]+c;
			m2[i][j]=s[i]-s[j]+d[i]+d[j]+c;
			m3[i][j]=-s[i]+s[j]+d[i]+d[j]+c;
			m4[i][j]=-s[i]-s[j]+d[i]+d[j]+c;
		} else m1[i][j]=m2[i][j]=m3[i][j]=m4[i][j]=-INF;
		if (i>1) update(m4[i][j],m4[i-1][j]); if (j>i+1) update(m4[i][j],m4[i][j-1]);
	}
	for (int len=2;len<=n;len++) for (int l=1,r;l+len-1<=n;l++) {
		r=l+len-1;
		if (r>l+1) update(m2[l][r],m2[l][r-1]),update(m2[l][r],m2[l+1][r]);
	}
	for (int len=n;len>=2;len--) for (int l=1,r;l+len-1<=n;l++) {
		r=l+len-1;
		if (l>1) update(m3[l][r],m3[l-1][r]); if (r<n) update(m3[l][r],m3[l][r+1]);
	}
	ll res=INF,t;
	for (int l=n;l>=1;l--) for (int r=n;r>=l+1;r--) {
		if (l+1<r) update(m1[l][r],m1[l+1][r]); if (r<n) update(m1[l][r],m1[l][r+1]);
		t=cmax(cmax(m1[l][r]-s[l]-s[r],m2[l][r]-s[l]+s[r]),cmax(m3[l][r]-s[r]+s[l],m4[l][r]+s[l]+s[r]));
		if (t<res) res=t;
	}
	//printf("%lld\n",res);
	return max(res,M);
}
ll find_shortcut(int N,vector<int> LLL,vector<int> DDD,int CCC) {
	n=N;
	for (int i=1;i<=n;i++) {
		if (i>1) s[i]=s[i-1]+LLL[i-2];
		d[i]=DDD[i-1];
	}
	c=CCC;
	D.push_back(0);
	for (int i=1;i<=n;i++) for (int j=i+1;j<=n;j++)
		D.push_back(s[j]-s[i]+d[i]+d[j]);
	sort(D.begin(),D.end());
	D.resize(unique(D.begin(),D.end())-D.begin());
	//for (ll x : D) printf("%lld ",x); puts("");
	int l=0,r=(int)D.size()-1,mid; ll res;
	while (l<=r) {
		mid=(l+r)>>1;
		ll t=solve(D[mid]);
		if (mid<(int)D.size()-1&&t>=D[mid+1]) l=mid+1;
		else res=t,r=mid-1;
	}
	//printf("HI %d %lld\n",res,solve(D[res]));
	//exit(0);
	return res;
	
}

Compilation message (stderr)

shortcut.cpp: In function 'll solve(ll)':
shortcut.cpp:21:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   21 |   if (i>1) update(m4[i][j],m4[i-1][j]); if (j>i+1) update(m4[i][j],m4[i][j-1]);
      |   ^~
shortcut.cpp:21:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   21 |   if (i>1) update(m4[i][j],m4[i-1][j]); if (j>i+1) update(m4[i][j],m4[i][j-1]);
      |                                         ^~
shortcut.cpp:29:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   29 |   if (l>1) update(m3[l][r],m3[l-1][r]); if (r<n) update(m3[l][r],m3[l][r+1]);
      |   ^~
shortcut.cpp:29:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   29 |   if (l>1) update(m3[l][r],m3[l-1][r]); if (r<n) update(m3[l][r],m3[l][r+1]);
      |                                         ^~
shortcut.cpp:33:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   33 |   if (l+1<r) update(m1[l][r],m1[l+1][r]); if (r<n) update(m1[l][r],m1[l][r+1]);
      |   ^~
shortcut.cpp:33:43: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   33 |   if (l+1<r) update(m1[l][r],m1[l+1][r]); if (r<n) update(m1[l][r],m1[l][r+1]);
      |                                           ^~
shortcut.cpp: In function 'll find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:62:9: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
   62 |  return res;
      |         ^~~

• Subtask 1: 9 / 9
• Subtask 2: 14 / 14
• Subtask 3: 8 / 8
• Subtask 4: 7 / 7
• Subtask 5: 0 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3