# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1007054 | amin | Closing Time (IOI23_closing) | C++17 | 1058 ms | 11968 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "closing.h"
#include <bits/stdc++.h>
#include <vector>
#define ll long long
using namespace std;
int max_score(int n, int x, int y, long long k,vector<int> u,vector<int> v,vector<int>w)
{
ll ans=2;
if(x>y)
swap(x,y);
int a=x;
int b=y;
vector<ll>val;
ll co=0;
//ll sum=0;
ll path=0;
for(int i=a;i<b;i++)
{
path+=w[i];
}
ll lena=0,lenb=0;
// int o=0;
while(a!=0||b!=n-1)
{
// cout<<co<<endl;
// cout<<a<<' '<<b<<endl;
ll h=1e18;
if(a!=0)
{h=min(h,lena+w[a-1]);
}
if(b!=n-1)
{
h=min(h,lenb+w[b]);
}
if(h>path)
{
while(co>0)
{
// cout<<"HERE"<<endl;
val.push_back(path);
co--;
}
}
if(a!=0&&b!=n-1)
{
if(w[a-1]<=w[b])
{
// cout<<"HERE"<<endl;
a--;
co++;
lena+=w[a];
val.push_back(lena);
continue;
}else
{
co++;
lenb+=w[b];
val.push_back(lenb);
b++;
continue;
}
}
if(a==0)
{
// cout<<"here"<<endl;
co++;
lenb+=w[b];
val.push_back(lenb);
b++;
continue;
}
if(b==n-1)
{
co++;
lena+=w[a-1];
val.push_back(lena);
a--;
}
}
while(co--)
val.push_back(path);
for(int i=0;i<val.size();i++)
{
if(i)
val[i]+=val[i-1];
}
ll suma[n];
a=x;
b=y;
for(int i=a;i<=b;i++)
{
if(i==a)
{
suma[i]=0;
continue;
}
//cout<<i<<' '<<w[i-1];
suma[i]=suma[i-1]+w[i-1];
// cout<<suma[i]<<endl;
}
//cout<<suma[a];
//cout<<"HERE"<<endl;
ll sumb[n];
for(int i=b;i>=a;i--)
{
if(i==b)
{
sumb[i]=0;
continue;
}
sumb[i]=sumb[i+1]+w[i];
// cout<<sumb[i]<<endl;
}
ll sum=0;
ll no=0;
a=x;
b=y;
for(int i=a;i<=b;i++)
{
sum=0;
for(int y=b-1;y>=i;y--)
{
sum+=sumb[y];
}
for(int y=a;y<=b;y++)
{
// cout<<i<<' '<<y<<endl;
// cout<<sum<<' ';
if(y>=i)
{
sum+=max(suma[y],sumb[y]);
sum-=sumb[y];
}else
sum+=suma[y];
// cout<<sum<<endl;
no=b-i+1-a+y+1;
if(sum>k)
continue;
ll j=k-sum;
auto u=upper_bound(val.begin(),val.end(),j);
if(u!=val.begin())
{
// u--;
no+=u-val.begin();
}
ans=max(ans,no);
// cout<<no<<endl;
}
}
return ans;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |