Submission #138419

#	Time	Username	Problem	Language	Result	Execution time	Memory
138419		arthurconmy	Shortcut (IOI16_shortcut)	C++14	0 / 100	2 ms	380 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<pair<int,int>> segs;
    vector<pair<ll,int>> diams;
    vector<ll> pref_sums(n+1);

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

    for(int i=1; i<=n; i++)
    {
    	for(int j=i; j<=n; j++)
    	{
    		segs.push_back({i,j});

    		if(i==j)
    		{
    			diams.push_back({ll(D[i-1]),segs.size()-1});
    		}

    		else diams.push_back({pref_sums[j]-pref_sums[i]+ll(D[j-1]+D[i-1]),segs.size()-1});
    	}
    }

    sort(diams.rbegin(),diams.rend());

    // for(auto d:diams)
    // {
    // 	cout << segs[d.second].first << " " << segs[d.second].second << endl;
    // 	cout << d.first << endl;
    // }

    diams.push_back({0,0}); // should add a buffer for 

    pair<int,int> active = {1,n};

    ll ans = diams[0].first;

    for(int i=0; i<int(diams.size())-1; i++)
    {
    	merger(active,segs[diams[i].second]);
    	if(active.first==-1) break;

    	ll savings = pref_sums[active.second]-pref_sums[active.first]-ll(c);

    	// cout << savings << endl;

    	ans = min(ans, max(diams[0].first - savings,diams[i+1].first));
    }

    return ans;
}

#ifdef ARTHUR_LOCAL
	int main()
	{
		cout << find_shortcut(4, {10, 20, 20}, {0, 40, 0, 30}, 10) << endl;
	}
#endif

• Subtask 1: 0 / 9
• Subtask 2: 0 / 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