Submission #773750

#	Time	Username	Problem	Language	Result	Execution time	Memory
773750		ttamx	Shortcut (IOI16_shortcut)	C++14	0 / 100	1 ms	340 KiB

shortcut

#include "shortcut.h"
#include<bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")

using namespace std;

typedef long long ll;

const int N=22;

int n;
ll c;
ll w[N],d[N];
ll dp[N][N];
ll ans=1e18;

ll calc(int x,int y){
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)dp[i][j]=1e18;
    for(int i=1;i<=n;i++)dp[i][i]=0;
    for(int i=1;i<n;i++)dp[i][i+1]=dp[i+1][i]=w[i];
    dp[x][y]=dp[y][x]=min(dp[x][y],c);
    for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
    ll res=0;
    for(int i=1;i<=n;i++)for(int j=1;j<i;j++)res=max(res,dp[i][j]+d[i]+d[j]);
    return res;
}

long long find_shortcut(int _n, vector<int> _w, vector<int> _d, int _c){
    n=_n,c=_c;
    for(int i=0;i<n-1;i++)w[i+1]=_w[i];
    for(int i=0;i<n;i++)d[i+1]=_d[i];
    for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)ans=min(ans,calc(i,j));
    return ans;
}

• 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