Submission #138428

#	Time	Username	Problem	Language	Result	Execution time	Memory
138428		arthurconmy	Shortcut (IOI16_shortcut)	C++14	23 / 100	2037 ms	396 KiB

shortcut

#include <bits/stdc++.h>
#ifndef ARTHUR_LOCAL
	#include "shortcut.h"
#endif
using namespace std;
using ll = long long;

void merger(pair<int,int> &a, pair<int,int> b)
{
	// cout << a.first << " " << a.second << endl;

	int from = max(a.first,b.first);
	int to = min(a.second,b.second);

	if(from>=to) a = {-1,-1};
	else a = make_pair(from,to);
}

ll find_shortcut(int n, vector<int> L, vector<int> D, int c)
{
    vector<ll> pref_sums(n+1);

    for(int i=1; i<n; i++)
    {
    	pref_sums[i]=pref_sums[i-1]+ll(L[i-1]);
    }

    ll ans = 1e18;

    for(int i=0; i<n; i++)
    {
    	for(int j=i+1; j<n; j++)
    	{
    		// shortcut is between i and j

    		ll cur_ans = 0;

    		for(int a=0; a<n; a++)
    		{
    			for(int b=a+1; b<n; b++)
    			{
    				ll cur = ll(D[a]+D[b]);

    				ll useb = pref_sums[max(b,j)]-pref_sums[min(b,j)];
    				useb += ll(c);
    				useb += pref_sums[max(a,i)]-pref_sums[min(a,i)];

    				cur += min(useb,pref_sums[b]-pref_sums[a]);
    			
    				cur_ans=max(cur_ans,cur);
    			}
    		}

    		// cout << i << " " << j << " " << cur_ans << endl;

    		ans=min(ans,cur_ans);
    	}
    }

    return ans;
}

#ifdef ARTHUR_LOCAL
	int main()
	{
		cout << find_shortcut(4, {10,10,10}, {10,10,10,10}, 1) << endl;
	}
#endif

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