oj.uz

Submission #71536

# Submission time Handle Problem Language Result Execution time Memory
71536 2018-08-25T04:47:33 Z gnoor Shortcut (IOI16_shortcut) C++17
0 / 100
 2 ms 432 KB 
#include "shortcut.h"

#include <vector>
#include <algorithm>

using namespace std;

struct ei {
	long long dis;
	pair<int,int> range;
};

bool operator< (const ei &a, const ei &b) {
	return a.dis>b.dis;
}

pair<int,int> comb(const pair<int,int> &a, const pair<int,int> &b) {
	if (b.first>a.second) return {-1,-1};
	return {max(a.first,b.first),min(a.second,b.second)};
}

long long find_shortcut(int n, vector<int> l, vector<int> d, int c)
{
	vector<long long> qs(n,0);
	for (int i=1;i<n;i++) {
		qs[i]=l[i];
		qs[i]+=qs[i-1];
	}
	vector<ei> tbl;
	tbl.reserve(n*(n-1)/2);
	long long ans=0;
	long long mx=0;
	for (int i=0;i<n;i++) {
		for (int j=i+1;j<n;j++) {
			tbl.push_back(ei{qs[j]-qs[i]+d[j]+d[i],{i,j}});
			mx=max(mx,qs[j]-qs[i]+d[j]+d[i]);
		}
	}
	ans=mx;
	sort(tbl.begin(),tbl.end());
	pair<int,int> cur={0,n-1};
	long long curans;
	long long red;
	for (int i=0;i<(int)tbl.size();i++) {
		cur=comb(cur,tbl[i].range);
		if (cur.first==-1) break;
		red=qs[cur.second]-qs[cur.first]-c;
		if (red<=0) break;
		if (i==(int)tbl.size()-1||tbl[i+1].dis!=tbl[i].dis) {			
			curans=mx-red;
			if (i!=(int)tbl.size()-1) {
				curans=max(curans,tbl[i+1].dis);
			}
			ans=min(ans,curans);
		}
	}
	return ans;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB n = 4, 80 is a correct answer
2 Correct 2 ms 356 KB n = 9, 110 is a correct answer
3 Correct 2 ms 432 KB n = 4, 21 is a correct answer
4 Incorrect 2 ms 432 KB n = 3, incorrect answer: jury 4 vs contestant 3

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB n = 4, 80 is a correct answer
2 Correct 2 ms 356 KB n = 9, 110 is a correct answer
3 Correct 2 ms 432 KB n = 4, 21 is a correct answer
4 Incorrect 2 ms 432 KB n = 3, incorrect answer: jury 4 vs contestant 3

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB n = 4, 80 is a correct answer
2 Correct 2 ms 356 KB n = 9, 110 is a correct answer
3 Correct 2 ms 432 KB n = 4, 21 is a correct answer
4 Incorrect 2 ms 432 KB n = 3, incorrect answer: jury 4 vs contestant 3

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB n = 4, 80 is a correct answer
2 Correct 2 ms 356 KB n = 9, 110 is a correct answer
3 Correct 2 ms 432 KB n = 4, 21 is a correct answer
4 Incorrect 2 ms 432 KB n = 3, incorrect answer: jury 4 vs contestant 3

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB n = 4, 80 is a correct answer
2 Correct 2 ms 356 KB n = 9, 110 is a correct answer
3 Correct 2 ms 432 KB n = 4, 21 is a correct answer
4 Incorrect 2 ms 432 KB n = 3, incorrect answer: jury 4 vs contestant 3

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB n = 4, 80 is a correct answer
2 Correct 2 ms 356 KB n = 9, 110 is a correct answer
3 Correct 2 ms 432 KB n = 4, 21 is a correct answer
4 Incorrect 2 ms 432 KB n = 3, incorrect answer: jury 4 vs contestant 3

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB n = 4, 80 is a correct answer
2 Correct 2 ms 356 KB n = 9, 110 is a correct answer
3 Correct 2 ms 432 KB n = 4, 21 is a correct answer
4 Incorrect 2 ms 432 KB n = 3, incorrect answer: jury 4 vs contestant 3

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB n = 4, 80 is a correct answer
2 Correct 2 ms 356 KB n = 9, 110 is a correct answer
3 Correct 2 ms 432 KB n = 4, 21 is a correct answer
4 Incorrect 2 ms 432 KB n = 3, incorrect answer: jury 4 vs contestant 3