Submission #787531

#	Time	Username	Problem	Language	Result	Execution time	Memory
787531		fatemetmhr	Shortcut (IOI16_shortcut)	C++17	23 / 100	2092 ms	380 KiB

shortcut

//  ~ Be Name Khoda ~  //

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

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  1e6   + 10;
const int maxn5 =  3e3   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   + 7;
const int lg    =  20;
const ll  inf   =  1e18;

int n;
ll c;
vector <ll> d;
ll ps[maxn5], ps2[maxn5];
set <pair<ll, int>> av;
vector <pair<int, ll>> adj[maxn5];

ll dis(int a, int b){
    if(a > b)
        swap(a, b);
    return ps[b] - ps[a];
}

long long find_shortcut(int N, std::vector<int> l, std::vector<int> D, int C)
{
    n = N;
    c = C;
    for(auto u : D)
        d.pb(u);
    ps[0] = 0;
    for(int i = 1; i < n; i++)
        ps[i] = ps[i - 1] + l[i - 1];
    ll mn = inf;
    for(int i = 0; i < n; i++) for(int j = 0; j < n; j++){
        ll mx = 0;
        for(int x = 0; x < n; x++) for(int y = x + 1; y < n; y++){
            mx = max(mx, d[x] + d[y] + min({dis(x, y), dis(x, i) + c + dis(y, j), dis(x, j) + c + dis(y, i)}));
            //cout << i << ' ' << j << ' ' << x << ' ' << y << ' ' << dis(x, y) << ' ' <<  dis(x, i) + c + dis(y, j) << ' ' << dis(x, j) + c + dis(y, i) << endl;
        }
        mn = min(mn, mx);
        //cout << i << ' ' << j << ' ' << mn << endl;
    }
    return mn;
}

• 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