Submission #789682

#	Time	Username	Problem	Language	Result	Execution time	Memory
789682		1ne	Shortcut (IOI16_shortcut)	C++14	31 / 100	2074 ms	1960 KiB

shortcut

#include <cstdio>
#include <cassert>
#include "shortcut.h"
#pragma once
#include <vector>
#include <bits/stdc++.h>
using namespace std;
struct node{
  long long x,y,d;
};
long long find_shortcut(int n, std::vector <int> ll, std::vector <int> d, int c){
	vector<long long>pref_max(n,0);
	vector<long long>suff_max(n,0);
	for (int i = 0 ;i<n;++i){
		if (i == 0){
			pref_max[i] = d[i];
		}
		else{
			pref_max[i] = max((long long)d[i],pref_max[i - 1] + ll[i - 1]);
		}
	}
	for (int i = n - 1;i>=0;--i){
		if (i == n - 1){
			suff_max[i] = d[i];
		}
		else{
			suff_max[i] = max((long long)d[i],suff_max[i + 1] + ll[i]);
		}
	}
	vector<long long>pref_seg(n,0);
	vector<long long>suff_seg(n,0);
	for (int i = 0;i<n;++i){
		if (i == 0){
			pref_seg[i] = d[i];
		}
		else{
			pref_seg[i] = max(pref_seg[i - 1],pref_max[i - 1] + ll[i - 1] + d[i]);
		}
	}
	for (int i = n - 1;i>=0;--i){
		if (i == n - 1){
			suff_seg[i] = d[i];
		}
		else{
			suff_seg[i] = max(suff_seg[i + 1],suff_max[i + 1] + ll[i] + d[i]);
		}
	}
	vector<long long>pref(n,0);
	for (int i = 0;i<n - 1;++i){
		pref[i + 1] = pref[i] + ll[i];
	}
	auto query = [&](int l,int r){
		if (l > r){
			swap(l,r);
		}
	  return pref[r] - pref[l];
	};	
	long long v = query(0,1);
	for (int i = 0;i<n - 1;++i){
		v = max(v,pref_max[i] + suff_max[i + 1] + ll[i]); 
	}
	auto check = [&](long long mid){
		vector<node>pos;
		for (int i = 0;i<n;++i){
			for (int j = i + 1;j<n;++j){
				if (d[i] + d[j] + query(i,j) > mid){
					pos.push_back({i,j,mid - d[i] - d[j] - c});
				}
			}
		}
		sort(pos.begin(),pos.end(),[&](auto x,auto y){
		  if (x.d == y.d)return x.y < y.y;
		  return x.d < y.d;
		});		
		for (int i = 0;i<n;++i){
			bool valid = true;
			for (int j = i + 1;j<n;++j){
				bool ok = true;
				for (auto x:pos){
					if (query(i,x.x) + query(j,x.y) <= x.d || query(i,x.y) + query(j,x.x) <= x.d){
						continue;
					}
					ok = false;
					if (x.y <= j){
						valid = false;		
					}
					break;
				}
				if (ok){
					return 1;
				}
				if (!valid)break;
			}
		}
		return 0;	
	};
	long long pos = 0;
	long long left = 0,right = 1e12;
	while(left<=right){
		long long mid = (left + right)>>1;
		if (check(mid)){
			right = mid - 1;
			pos = mid;
		}
		else{
			left = mid + 1;
		}
	}
	return pos;
}

Compilation message (stderr)

shortcut.cpp:4:9: warning: #pragma once in main file
    4 | #pragma once
      |         ^~~~

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