Submission #1136976

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136976		the_coding_pooh	Shortcut (IOI16_shortcut)	C++20	0 / 100	0 ms	324 KiB

shortcut

#include "shortcut.h"
#include <bits/stdc++.h>

#define uwu return

using namespace std;

const int SIZE = 1e6 + 5;

const long long INF = 1e18 + 7;

long long pre[SIZE];
long long pre_max[SIZE], suf_max[SIZE];

vector <int> d;

long long calc_in(int l, int r, int c){
	long long ret = 0;
	for(int i = l; i <= r; i++){
		for(int j = i; j <= r; j++){
			ret = max(ret, min(pre[j] - pre[i], pre[r] - pre[j] + pre[i] - pre[l] + c) + d[i] + d[j]);
		}
	}
	return ret;
}

long long calc_n(int l, int r){
	long long ret = 0;
	for(int i = l; i <= r; i++){
		for(int j = i; j <= r; j++){
			ret = max(ret, pre[j] - pre[i] + d[i] + d[j]);
		}
	}
	return ret;
}

long long find_shortcut(int n, vector<int> l, vector<int> _d, int c){
	n--;
	d = _d;
	for(int i = 1; i <= n; i++){
		pre[i] = l[i] + pre[i - 1];
	}
	pre_max[0] = d[0];
	for(int i = 1; i <= n; i++){
		pre_max[i] = max(pre_max[i - 1], d[i] - pre[i]);
	}
	suf_max[n] = d[n] + pre[n];
	for(int i = n - 1; i >= 0; i--){
		suf_max[i] = max(suf_max[i + 1], d[i] + pre[i]);
	}
	long long now_ans = INF, ans = INF;
	for(int l = 0, r = 0; l < n; l++){
		while(r < n){
			r++;
			long long tmp = max({pre_max[l] + suf_max[r] + min(0LL, c - pre[r] + pre[l]), calc_in(l, r, c), calc_n(0, l), calc_n(r, n)});
			if(tmp > now_ans){
				r--;
				break;
			}
			else
				now_ans = tmp;
		}
		ans = min(now_ans, ans);
		  //  cout << l << ' ' << r << ' ' << now_ans << '\n';
		if(l < n)
			now_ans = max({pre_max[l + 1] + suf_max[r] + min(0LL, c - pre[r] + pre[l + 1]), calc_in(l + 1, r, c), calc_n(0, l + 1), calc_n(r, n)});
	}
	uwu ans;
}

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: 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