oj.uz

답안 #85097

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
85097 2018-11-18T13:42:02 Z SirCeness 모임들 (IOI18_meetings) C++14
4 / 100
 5500 ms 3384 KB 
#include "meetings.h"
#include <bits/stdc++.h>

using namespace std;

map<long long, long long> m;

long long get(vector<int> H, int l, int r){
	//cout << "get(" << l << ", " << r << ")" << endl;
	if (m.find(l*750000 + r) != m.end()) return m.find(l*750000+r) -> second;
	if (l == r) return H[l];
	if (l > r) return 0;
	int size = r-l+1;
	long long maxx = 0;
	for (int i = l; i <= r; i++){
		if (maxx < H[i]) maxx = H[i];
	}
	vector<long long> maxs;
	for (int i = l; i <= r; i++){
		if (H[i] == maxx) maxs.push_back(i);
	}
	
	long long min = get(H, l, maxs[0]-1) + maxx*(size - maxs[0] + l);
	for (int i = 1; i < maxs.size(); i++){
		long long a = get(H, maxs[i-1]+1, maxs[i]-1) + maxx*(size - maxs[i] + maxs[i-1] + 1);
		if (a < min) min = a;
	}
	long long a = get(H, maxs[maxs.size()-1]+1, r) + maxx*(size - (r - (maxs[maxs.size()-1]+1) + 1));
	if (a < min) min = a;
	m.insert(make_pair(l*750000+r, min));
	return min;
	
}

vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
	//cout << "basla" << endl;
	
	int Q = L.size();
	vector<long long> ret(Q);
	
	for (int i = 0; i < Q; i++){
		ret[i] = get(H, L[i], R[i]);
	}
	
	return ret;
}

/*
vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
  int Q = L.size();
  std::vector<long long> C(Q);
  for (int j = 0; j < Q; ++j) {
    C[j] = H[L[j]];
  }
  return C;
}
*/

Compilation message

meetings.cpp: In function 'long long int get(std::vector<int>, int, int)':
meetings.cpp:24:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < maxs.size(); i++){
                  ~~^~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 6 ms 736 KB Output is correct
3 Correct 6 ms 760 KB Output is correct
4 Correct 6 ms 628 KB Output is correct
5 Correct 7 ms 700 KB Output is correct
6 Correct 4 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 4 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 6 ms 736 KB Output is correct
3 Correct 6 ms 760 KB Output is correct
4 Correct 6 ms 628 KB Output is correct
5 Correct 7 ms 700 KB Output is correct
6 Correct 4 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 4 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 234 ms 3384 KB Output is correct
11 Correct 93 ms 1312 KB Output is correct
12 Correct 196 ms 2816 KB Output is correct
13 Correct 180 ms 1184 KB Output is correct
14 Execution timed out 5553 ms 836 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Execution timed out 5585 ms 1868 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Execution timed out 5585 ms 1868 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 6 ms 736 KB Output is correct
3 Correct 6 ms 760 KB Output is correct
4 Correct 6 ms 628 KB Output is correct
5 Correct 7 ms 700 KB Output is correct
6 Correct 4 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 4 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 234 ms 3384 KB Output is correct
11 Correct 93 ms 1312 KB Output is correct
12 Correct 196 ms 2816 KB Output is correct
13 Correct 180 ms 1184 KB Output is correct
14 Execution timed out 5553 ms 836 KB Time limit exceeded
15 Halted 0 ms 0 KB -