Submission #1209889

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209889		ansori	Shortcut (IOI16_shortcut)	C++20	71 / 100	286 ms	1348 KiB

shortcut

#include "shortcut.h"
#include<bits/stdc++.h>
#define ll long long
const int N = 3e3 + 5;
const ll inf = 1e16;
using namespace std;
ll ans , C;
vector<ll> ds;
vector<int> l , d;
bool ok(ll dst){
	ll mndif = -inf , mxdif = inf , mnsum = -inf , mxsum = inf; 
	int n = d.size();
	for(int i = 0;i < n; ++ i){
		for(int j = i + 1;j < n; ++ j){
			if(ds[j] - ds[i] + d[j] + d[i] <= dst) continue ;
			ll dif = dst - d[i] - d[j] - C;
			mndif = max(mndif , ds[j] - ds[i] - dif);
			mxdif = min(mxdif , ds[j] - ds[i] + dif);
			mnsum = max(mnsum , ds[j] + ds[i] - dif);
			mxsum = min(mxsum , ds[j] + ds[i] + dif);
		}
	}
	for(int i = 0;i < n; ++ i){
		for(int j = i + 1;j < n; ++ j){
			if(ds[j] - ds[i] < mndif) continue ;
			if(ds[j] - ds[i] > mxdif) continue ;
			if(ds[j] + ds[i] < mnsum) continue ;
			if(ds[j] + ds[i] > mxsum) continue ;
			return 1;
		}
	}
	return 0;
}
long long find_shortcut(int n, std::vector<int> lenth, std::vector<int> dist , int c)
{
	C = c;
	l = lenth;
	d = dist;
	if(n > 3e3){
		//XD
		return -1;
	}
	ds = vector<ll> (n , 0);
	for(int i = 1;i < n; ++ i) ds[i] = ds[i - 1] + l[i - 1];
	ll l = 0;
	ll r = inf + 1;
	while(l + 1 < r){
		ll mid = (l + r) / 2;
		if(ok(mid)) r = mid;
		else l = mid;
	}
    return r;
}

Compilation message (stderr)

shortcut.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
shortcut_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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