Submission #1031594

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031594		pcc	Shortcut (IOI16_shortcut)	C++17	0 / 100	1 ms	604 KiB

shortcut

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

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC taget("avx2,popcnt,sse4")

#define pll pair<ll,ll>
#define fs first
#define sc second
#define pii pair<int,int>
#define ll long long

#define DEBUG(T) cerr<<#T<<":"<<T<<endl;

const ll inf = 1e18;
const int mxn = 255;
ll pref[mxn];
ll arr[mxn];
int C,N;
int trans[mxn];
vector<pll> paths[mxn];
ll dp[mxn][mxn];

ll dist[mxn];
namespace DIJKSTRA{
	priority_queue<pll,vector<pll>,greater<pll>> pq;
	void GO(int s){
		fill(dist,dist+mxn,inf);
		dist[s] = arr[s];
		pq.push(pll(arr[s],s));
		while(!pq.empty()){
			auto [d,now] = pq.top();
			pq.pop();
			if(dist[now] != d)continue;
			for(auto [nxt,w]:paths[now]){
				if(dist[nxt]>d+w){
					dist[nxt] = d+w;
					pq.push(pll(dist[nxt],nxt));
				}
			}
		}
		return;
	}
}

ll calc(int a,int b){
	paths[b].push_back(pll(a,C));
	paths[a].push_back(pll(b,C));
	ll ans = 0;
	for(int i = 0;i<N;i++){
		DIJKSTRA::GO(i);
		for(int j = 0;j<N;j++)if(j != i)dist[j] += arr[j];
		ans = max(ans,*max_element(dist,dist+N));
	}
	paths[a].pop_back();
	paths[b].pop_back();
	return ans;
}

long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c){
	N = n,C = c;
	for(int i = 0;i+1<N;i++){
		pref[i+1] = pref[i]+l[i];
	}
	for(int i = 1;i<N;i++){
		paths[i].push_back(pll(i-1,pref[i]-pref[i-1]));
		paths[i-1].push_back(pll(i,pref[i]-pref[i-1]));
	}
	for(int i = 0;i<N;i++)arr[i] = d[i];
	ll ans = inf;
	for(int i = 0;i<N;i++){
		for(int j = 0;j<=i;j++){
			dp[j][i] = calc(j,i);
			ans = min(ans,dp[j][i]);
		}
	}
	for(int i = 1;i<N;i++){
		for(int j = 0;j<i;j++){
			if(dp[trans[i]][i]<dp[j][i])trans[i] = j;
		}
	}
	for(int i = 1;i<N;i++){
		assert(trans[i] >= trans[i-1]);
	}
	return ans;
}

Compilation message (stderr)

shortcut.cpp:6: warning: ignoring '#pragma GCC taget' [-Wunknown-pragmas]
    6 | #pragma GCC taget("avx2,popcnt,sse4")
      |

• 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