Submission #1117774

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117774		vjudge1	Paprike (COI18_paprike)	C++17	0 / 100	25 ms	9028 KiB

paprike

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int sz=2e5+5;

const int MOD=1e9+7;

const int INF=1e18;

int arr[sz];

vector<int> graph[sz];

void solve()
{
	int n,m;
	
	cin>>n>>m;
	
	for(int i=0;i<n;i++)
	    cin>>arr[i];
	
	for(int i=1;i<n;i++)
	{
	    int a,b;
	    
	    cin>>a>>b;
	    
	    a--;
	    
	    b--;
	    
	    graph[a].push_back(b);
	    
	    graph[b].push_back(a);
	}
	
	int l=0,r=n-1,sum=0;
	
	for(int i=0;i<n;i++)
	    sum+=arr[i];
	
	while(sum>m)
	{
	    if(arr[l]<arr[r])
	    {
	        sum-=arr[r];
	        
	        r--;
	    }
	    
	    else
	    {
	        sum-=arr[l];
	        
	        l++;
	    }
	}
	
	cout<<n-(r-l+1);
}

signed main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int t=1;

	//cin>>t;

	while(t--)
	{
		solve();
	}
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 13
• Subtask 3: 0 / 27
• Subtask 4: 0 / 49