Submission #1069590

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069590		UmairAhmadMirza	Closing Time (IOI23_closing)	C++17	9 / 100	40 ms	14944 KiB

closing

#include <bits/stdc++.h>
using namespace std;

#define ll long long
int const N=3005;

ll Xd[N],Yd[N],Mxd[N],Mnd[N],sim[N];
vector<ll> dst,st;

int max_score(int n, int X, int Y, long long K, vector<int> U,
              vector<int> V, vector<int> W)
{
	vector<int> wei(n+1,0);
	for(int i=0;i<n;i++)
		wei[i+1]=W[i];
	X++;
	Y++;
	for(int i=X+1;i<=n;i++)
		Xd[i]=Xd[i-1]+wei[i-1];
	for(int i=X-1;i>=1;i--)
		Xd[i]=Xd[i+1]+wei[i];
	for(int i=Y+1;i<=n;i++)
		Yd[i]=Yd[i-1]+wei[i-1];
	for(int i=Y-1;i>=1;i--)
		Yd[i]=Yd[i+1]+wei[i];
	for (int i = 1; i <=n; ++i){
		Mxd[i]=max(Xd[i],Yd[i]);
		Mnd[i]=min(Xd[i],Yd[i]);
		sim[i]=sim[i-1]+Mnd[i];
	}
	ll t=Xd[Y];
	for (int i = X; i <=Y; ++i)
		dst.push_back(Mxd[i]-Mnd[i]);
	sort(dst.begin(), dst.end());
	for (int i = 1; i < dst.size(); ++i)
		dst[i]+=dst[i-1];
	for (int i = 1; i <=n; ++i)
		st.push_back(Mnd[i]);
	sort(st.begin(), st.end());
	for (int i = 1; i < n; ++i)
		st[i]+=st[i-1];
	int ans=upper_bound(st.begin(), st.end(),K)-st.begin();
	for(int l=1;l<=X;l++)
		for(int r=Y;r<=n;r++){
			ll ot=(X-l)+(r-Y);
			ll cost=K-(sim[r]-sim[l-1]);
			if(cost<0)
				continue;
			int cnt=(r-l)+1;
			int ind=upper_bound(dst.begin(), dst.end(),cost)-dst.begin();
			cnt+=ind;
			if(ind==dst.size()){
				cost-=dst.back();
				cnt+=min(ot,cost/t);
			}
			ans=max(ans,cnt);
		}
	return ans;
}

Compilation message (stderr)

closing.cpp: In function 'int max_score(int, int, int, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:35:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |  for (int i = 1; i < dst.size(); ++i)
      |                  ~~^~~~~~~~~~~~
closing.cpp:52:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |    if(ind==dst.size()){
      |       ~~~^~~~~~~~~~~~

• Subtask 0: 0 / 0
• Subtask 1: 0 / 8
• Subtask 2: 9 / 9
• Subtask 3: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 9
• Subtask 6: 0 / 11
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 17