백준 10875 - 뱀
더보기
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
//(2,4) - (2,10) 은 is_row = false, axis=2, min = 4, max= 10 으로 표현
struct Line
{
bool is_row;
int axis, min, max;
bool operator < (const Line& rhs) const
{
if(this->axis == rhs.axis)
return this->max < rhs.max;
return this->axis < rhs.axis;
}
};
bool cross(const Line& a, const Line& b)
{
if (a.is_row == b.is_row)
{
if (a.axis != b.axis) return false;
if (a.min < b.min && a.max < b.min) return false;
if (b.max < a.min && b.max < a.max) return false;
return true;
}
else
{
if (b.min <= a.axis && a.axis <= b.max &&
a.min <= b.axis && b.axis <= a.max)
return true;
return false;
}
}
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
set<Line> rows, columns;
int L, N;
int dir = 3; //0 3 6 9 시계방향을 나타냄
int cur_x = 0, cur_y = 0;
long long len = 1;
bool has_collide = false;
cin >> L >> N;
rows.emplace(Line{true, 0,0,0});
columns.emplace(Line{ false, 0,0,0 });
for(int i =0;i<=N;++i)
{
int cur_len = 0;
int n; char d;
//i == N 인 경우는 다 돌고나서 죽을때까지 전진하는거
if(i!=N)
cin >> n >> d;
else
{
n = 2 * L;
d = 'L';
}
bool is_row = (dir == 3 || dir == 9); //3시 9시면 row겠지
int min, max, axis;
if (is_row)
{
axis = cur_y;
if(dir==3) //3시방향이면
{
min = cur_x + 1;
max = cur_x + n;
cur_x = max;
}
else //9시방향이면
{
max = cur_x - 1;
min = cur_x - n;
cur_x = min;
}
}
else
{
axis = cur_x;
if(dir == 0) //0시방향이면
{
min = cur_y + 1;
max = cur_y + n;
cur_y = max;
}
else
{
max = cur_y - 1;
min = cur_y - n;
cur_y = min;
}
}
Line line{ is_row, axis, min ,max }; //일단 라인을 만들어준다.
//------자기 자신한테 박는 경우 체크------
set<Line>* same_dir;
set<Line>* other_dir;
if(is_row)
{
same_dir = &rows;
other_dir = &columns;
}
else
{
same_dir = &columns;
other_dir = &rows;
}
//방향이 같은 애들 검사
for(auto collider : (*other_dir)) //이부분... lower_bound와 upper_bound를 써서 더 빨리 계산할 수 있으나 어쩌피 4ms로 성공함.
{
if(cross(line, collider))
{
//다른 방향에 박음
if (dir == 0 || dir == 3)
max = std::min(collider.axis - 1,max); //왜 min, max를 썻는가? => 길이는 줄어드는 방향으로만 갱신됨.
else
min = std::max(collider.axis + 1, min);
has_collide = true;
}
}
if(false == has_collide)
{
for (auto collider : (*same_dir))
{
if (cross(line, collider))
{
if (dir == 0 || dir == 3)
max = std::min(collider.min - 1, max);
else
min = std::max( collider.max + 1, min);
has_collide = true;
}
}
}
//자신한테는 안 박았다. 마지막으로 벽에 박는 경우 체크
if(has_collide == false)
{
if (min < -L)
{
min = -L;
has_collide = true;
}
else if (max > L)
{
max = L;
has_collide = true;
}
}
//최대로 갈 수 있는 거리가 계산된다.
len += max - min + 1;
//움직인 line을 저장해준다.
same_dir->emplace(line);
if (has_collide) break;
//방향 틀어주기
if (d == 'L')
{
if (dir == 0) dir = 9;
else dir -= 3;
}
else
{
if (dir == 9) dir = 0;
else dir += 3;
}
}
cout << len << endl;
return 0;
}
백준 5149 - 북서풍 (스위핑 알고리즘)
더보기
#include <iostream>
#include <vector>
#include <algorithm>
typedef std::pair<int, int> P;
using namespace std;
class SegTree
{
public:
SegTree(int size)
{
size_ = size ;
tree_.resize(size + 1, 0); //1부터 시작할거임.
}
void add(int i, int num = 1)
{
while(i<=size_)
{
tree_[i] += num;
i += (i & -i);
}
}
//from(inclusive) 부터 끝까지의 합을 구함
int sum_from_to_max(int from)
{
return sum(size_) - sum(from - 1);
}
private:
//1부터 i까지의 합
int sum(int i)
{
int sum = 0;
while(i>0)
{
sum += tree_[i];
i -= (i & -i);
}
return sum;
}
private:
vector<int> tree_;
int size_;
};
long long solve()
{
int num_island;
cin >> num_island;
vector<P> points;
points.reserve(num_island);
for(int i=0;i<num_island;++i)
{
int x, y;
cin >> x >> y;
points.emplace_back(x, y);
}
//Y값 재설정
sort(points.begin(), points.end(), [](P &a, P& b) { return a.second < b.second; });
int newY = 1, prev = points[0].second;
for(int i=0;i<num_island;++i)
{
if (points[i].second > prev)
{
++newY;
prev = points[i].second;
}
points[i].second = newY;
}
//X에 대해 오름차순으로, Y에 대해 내림차순으로 정렬.
sort(points.begin(), points.end(), [](P &a, P& b) { return a.first == b.first ? a.second > b.second : a.first < b.first; });
int maxY = newY;
SegTree seg_tree(maxY);
long long answer = 0;
for(auto & p : points)
{
answer += seg_tree.sum_from_to_max(p.second);
seg_tree.add(p.second);
}
return answer;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int num_tc;
cin >> num_tc;
while (num_tc-- > 0)
cout << solve() << endl;
return 0;
}백준 5670 - 휴대폰 자판 (트라이)
더보기
#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
using namespace std;
struct Node
{
Node()
{
for (int i = 0; i < 26; ++i)
next[i] = nullptr;
}
~Node()
{
for (int i = 0; i < 26; ++i)
if (next[i] != nullptr)
delete next[i];
}
Node* next[26];
int size = 0;
bool isEnd = false;
};
struct Trie
{
void insert(const string & str);
int count(const string & str);
Node head;
};
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
cout << fixed;
cout.precision(2);
int n;
while (cin >> n)
{
vector<string> strings;
strings.reserve(n);
for (int i = 0; i < n; ++i)
{
string str;
cin >> str;
strings.emplace_back(str);
}
Trie trie;
for (const auto & str : strings)
trie.insert(str);
int sum = 0;
for (const auto & str : strings)
sum += trie.count(str);
cout << sum / static_cast<double>(n) << "\n";
}
return 0;
}
void Trie::insert(const string& str)
{
Node * cur = &head;
for (auto ch : str)
{
const int idx = ch - 'a';
if (cur->next[idx] == nullptr)
{
cur->next[idx] = new Node();
cur->size++;
}
cur = cur->next[idx];
}
cur->isEnd = true;
}
int Trie::count(const string& str)
{
int cnt = 0;
if (head.size == 1) //처음은 한 번 치긴 해야함
++cnt;
Node * cur = &head;
for (auto ch : str)
{
const int idx = ch - 'a';
if (cur->isEnd || cur->size != 1)
++cnt;
cur = cur->next[idx];
}
return cnt;
}백준 3392 - 화성 지도 (스위핑)
더보기
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
constexpr int SIZE = 30001;
struct Line
{
Line(int x,int y1, int y2, int is_in) : x(x), y1(y1), y2(y2), is_in(is_in){}
int x, y1, y2, is_in;
};
class SegTree
{
public:
SegTree(int size)
{
tree_.resize(size << 2, 0);
cnt_.resize(size << 2, 0);
}
void update(int lo, int hi, int val, int node, int x, int y)
{
if (y < lo || hi < x) return;
if(lo <= x && y <= hi)
{
cnt_[node] += val;
}
else
{
int mid = (x + y) / 2;
update(lo, hi, val, node*2, x, mid);
update(lo, hi, val, node * 2 + 1, mid + 1, y);
}
if (cnt_[node] > 0)
tree_[node] = y - x + 1;
else if (x == y)
tree_[node] = 0;
else
tree_[node] = tree_[node * 2] + tree_[node * 2 + 1];
}
int height()
{
return tree_[1];
}
private:
vector<int> cnt_; //몇겹이 쌓였는지..
vector<int> tree_; //하나 하나는 0아니면 1
};
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int N;
cin >> N;
vector<Line> lines;
lines.reserve(2 * N);
for(int i=0;i<N;++i)
{
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
lines.emplace_back(x1, y1, y2 - 1, 1);
lines.emplace_back(x2, y1, y2 - 1, -1);
}
//x순으로 정렬
sort(lines.begin(), lines.end(), [](const Line& lhs, const Line& rhs) {return lhs.x < rhs.x; });
SegTree tree(SIZE);
int answer = 0;
int prev_x = 0;
tree.update(lines[0].y1, lines[0].y2, lines[0].is_in, 1, 0, SIZE);
prev_x = lines[0].x;
for(int i=1;i<lines.size();++i)
{
auto& line = lines[i];
const int width = line.x - prev_x;
answer += width * tree.height();
tree.update(line.y1, line.y2, line.is_in, 1, 0, SIZE);
prev_x = line.x;
}
cout << answer;
return 0;
}
백준 12846 - 무서운 아르바이트 (분할 정복)
더보기
#include <iostream>
#include <vector>
#include <stack>
typedef std::pair<int, int> Pay;
using namespace std;
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int N;
cin >> N;
vector<Pay> pays(N+1);
for (int i = 0; i < N; ++i)
{
pays[i].first = i;
cin >> pays[i].second;
}
pays[N].first = N;
pays[N].second = -1;
stack<Pay> stk;
long long ans = 0;
for(int i=0;i<pays.size();++i)
{
auto pay = pays[i];
int idx = pay.first;
int val = pay.second;
while(false == stk.empty() && stk.top().second >= pay.second)
{
const auto top = stk.top(); stk.pop();
const long long new_ans = (pay.first - top.first) * top.second;
if (ans < new_ans)
ans = new_ans;
idx = top.first;
val = pay.second;
}
stk.push(make_pair(idx, val));
}
cout << ans;
return 0;
}백준 10999 - 구간 합 구하기 2 (lazy propagation)
더보기
#include <iostream>
#include <vector>
using namespace std;
constexpr int TREE_SIZE = 1 << 21;
struct LazySegTree
{
public:
LazySegTree(int size)
{
start = size / 2;
arr.resize(size, 0);
lazy.resize(size, 0);
}
void set_values(vector<int> & leafs)
{
for (int i = 0; i < leafs.size(); ++i)
arr[start + i] = leafs[i];
for(int i= start -1; i>0; --i)
arr[i] = arr[i * 2] + arr[i * 2 + 1];
}
void add_values(int s, int e, int val) { add_values(s, e, 1, 1, start, val); }
long long sum(int s, int e) { return sum(s, e, 1, 1, start); }
private:
void propagate(int nodeIdx, int ns, int ne)
{
if(lazy[nodeIdx] != 0)
{
if(nodeIdx < start)
{
lazy[nodeIdx * 2] += lazy[nodeIdx];
lazy[nodeIdx * 2 + 1] += lazy[nodeIdx];
}
arr[nodeIdx] += lazy[nodeIdx] * (ne - ns + 1);
lazy[nodeIdx] = 0;
}
}
void add_values(int s, int e, int nodeIdx, int ns, int ne, int val)
{
propagate(nodeIdx, ns, ne); //왜?
if (s > ne || e < ns) return;
if(s <= ns && ne <= e)
{
lazy[nodeIdx] += val;
propagate(nodeIdx, ns, ne);
return;
}
const int mid = (ns + ne) / 2;
const int left = nodeIdx * 2;
const int right = nodeIdx * 2 + 1;
add_values(s, e, left, ns, mid , val);
add_values(s, e, right, mid + 1, ne, val);
arr[nodeIdx] = arr[left] + arr[right];
}
long long sum(int s, int e, int nodeIdx, int ns, int ne)
{
propagate(nodeIdx, ns, ne);
if (e < ns || ne < s) return 0;
if (s <= ns && ne <= e) return arr[nodeIdx];
int mid = (ne + ns) / 2;
return sum(s, e, nodeIdx * 2, ns, mid ) + sum(s, e, nodeIdx * 2 + 1, mid + 1, ne);
}
private:
vector<long long> arr, lazy;
int start = 0;
};
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int N, M, K;
cin >> N >> M >> K;
vector<int> leafs(N, 0);
for (int i = 0; i < N; ++i)
cin >> leafs[i];
LazySegTree seg(TREE_SIZE);
seg.set_values(leafs);
for(int i=0;i<M+K;++i)
{
int mode;
cin >> mode;
if(mode == 1)
{
int s, e, val;
cin >> s >> e >> val;
seg.add_values(s, e, val);
}
else //mode == 2
{
int s, e;
cin >> s >> e;
cout << seg.sum(s, e) << "\n";
}
}
return 0;
}프로그래머스 - 양궁대회 (백트래킹)
더보기
#include <vector>
using namespace std;
class Solver
{
public:
Solver(int n, vector<int>& info) : info_(info), n_(n), max_(-1)
{
numInfo_ = info.size();
answer_.resize(numInfo_,0);
}
vector<int> solve()
{
vector<int> scores(numInfo_, 0);
search(0, n_, scores);
if (max_ <= 0)
return vector<int>(1, -1);
else
return answer_;
}
private:
void search(int i, int left, vector<int>& scores)
{
//leaf임
if(i==numInfo_ - 1)
{
scores[i] = left;
int deltaScore = 0;
for(int i=0;i<numInfo_ - 1;++i)
{
if (scores[i] > info_[i])
deltaScore += 10 - i;
else if(info_[i]!=0)
deltaScore -= 10 - i;
}
if(deltaScore > max_) //dfs를 승리부터 돌려줄거라 결국 뒤늦게 온 경우 = 낮은 점수에 화살 많이 맞춘 경우
{
max_ = deltaScore;
setAnswer(scores);
}
else if(deltaScore == max_)
{
if (canSetAnswer(scores))
setAnswer(scores);
}
return;
}
if(left > info_[i])
{
scores[i] = info_[i] + 1;
search(i + 1, left - info_[i] - 1, scores);
}
scores[i] = 0;
search(i + 1, left, scores);
}
bool canSetAnswer(vector<int>& ans)
{
for (int i = numInfo_ - 1; i >= 0; --i)
{
if (ans[i] > answer_[i]) break; //새로운 정답이 낮은 점수 갯수가 더 많음.
if (ans[i] < answer_[i]) return false; //기존꺼가 더 정답임
}
return true;
}
void setAnswer(vector<int>& ans)
{
for (int i = 0; i < numInfo_; ++i)
answer_[i] = ans[i];
}
int numInfo_;
int n_;
int max_;
vector<int> answer_;
vector<int>& info_;
};
vector<int> solution(int n, vector<int> info) {
Solver solver(n, info);
return solver.solve();
}백준 13544 - 수열과 쿼리 3 (머지 소트 트리)
더보기
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const int SIZE = 1 << 18;
struct MergeSortTree
{
public:
MergeSortTree() { tree.resize(SIZE); }
void ReadAndConstruct(istream & in, int cnt_leaf);
int Query(int i, int j, int k);
private:
int Query(int s, int e, int k, int node, int ns , int ne);
void ReadLeafs(istream & in, int cnt_leaf);
void Construct();
vector<vector<int>> tree;
int cntLeafs_ = 0;
};
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int last_ans = 0;
int N, M;
cin >> N;
MergeSortTree tree;
tree.ReadAndConstruct(cin, N);
//QUER
cin >> M;
int iter_cnt = M;
while(iter_cnt-->0)
{
int a, b, c;
cin >> a >> b >> c;
const int i = a ^ last_ans;
const int j = b ^ last_ans;
const int k = c ^ last_ans;
last_ans = tree.Query(i, j, k);
cout << last_ans << "\n";
}
return 0;
}
int MergeSortTree::Query(int i, int j, int k)
{
return Query(i - 1, j, k, 1, 0, SIZE / 2);
}
int MergeSortTree::Query(int s, int e, int k, int node, int ns, int ne)
{
if (ne <= s || e <= ns) return 0;
if (s <= ns && ne <= e)
return tree[node].end() - upper_bound(tree[node].begin(), tree[node].end(), k);
int mid = (ns + ne) / 2;
return Query(s, e, k, node * 2, ns, mid) + Query(s, e, k, node * 2 + 1, mid, ne);
}
void MergeSortTree::ReadAndConstruct(istream & in, int cnt_leaf)
{
ReadLeafs(in, cnt_leaf);
Construct();
}
void MergeSortTree::ReadLeafs(istream& in, int cnt_leaf)
{
cntLeafs_ = cnt_leaf;
int leaf_start = SIZE / 2;
for (int i = 0; i < cnt_leaf; ++i)
{
int val;
in >> val;
tree[leaf_start + i].emplace_back(val);
}
}
void MergeSortTree::Construct()
{
int leaf_start = SIZE / 2;
for(int i=leaf_start - 1; i> 0 ; --i)
{
auto & left = tree[i * 2];
auto & right = tree[i * 2 + 1];
auto & cur = tree[i];
int size = left.size() + right.size();
cur.resize(size);
//머지 소트의 머지 수행
int idxL = 0, idxR = 0;
for(int j =0;j<size;++j)
{
if (idxR >= right.size() || (idxL < left.size() && left[idxL] < right[idxR]))
cur[j] = left[idxL++];
else
cur[j] = right[idxR++];
}
}
}프로그래머스 - 양과 늑대 (비트마스킹)
더보기
#include <vector>
#include <list>
using namespace std;
class Solver
{
public:
Solver(const vector<int>& info,const vector<vector<int>>& edges) : info_(info)
{
adjs_.resize(info.size());
for (const auto & edge : edges)
adjs_[edge[0]].emplace_back(edge[1]);
}
int Solve()
{
list<int> emptyList;
dfs(0, 0, 0, emptyList);
return maxSheepNum_;
}
private :
void dfs(int curIdx, int numSheeps, int numWolves, list<int> nextNodes)
{
if (info_[curIdx] == 1)
{
++numWolves;
if (numSheeps <= numWolves) return;
}
else
{
++numSheeps;
if (numSheeps > maxSheepNum_) maxSheepNum_ = numSheeps;
}
list<int> newNextNodes(nextNodes);
for (auto adj : adjs_[curIdx])
newNextNodes.emplace_back(adj);
newNextNodes.remove(curIdx);
for(auto next : newNextNodes)
dfs(next , numSheeps, numWolves, newNextNodes);
}
private :
const vector<int>& info_;
vector<vector<int>> adjs_;
int maxSheepNum_ = 0;
};
int solution(vector<int> info, vector<vector<int>> edges) {
Solver solver(info, edges);
return solver.Solve();
}백준 1208 : 부분수열의 합 2 (Meet in the middle)
더보기
#include <iostream>
#include <vector>
using namespace std;
int N, S;
vector<int> arr;
long long result = 0;
vector<int> sumMap;
const int MAX_SUM = 4000001;
void dfs1(int from, int to, int sum)
{
if(from == to)
{
const int sumMapIdx = sum + MAX_SUM;
sumMap[sumMapIdx]++;
return;
}
dfs1(from + 1, to, sum); //지금꺼 안 넣음
dfs1(from + 1, to, sum + arr[from]) ; //지금꺼 넣음
}
void dfs2(int from, int to, int sum)
{
if(from == to)
{
const int sumMapIdx = S - sum + MAX_SUM;
result += sumMap[sumMapIdx];
return;
}
dfs2(from + 1, to, sum); //지금꺼 안 넣음
dfs2(from + 1, to, sum+arr[from]); //지금꺼 넣음
}
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
cin >> N >> S;
sumMap.resize(MAX_SUM * 2, 0);
arr.resize(N);
for (int i = 0; i < N; ++i)
cin >> arr[i];
const int half = N / 2;
dfs1(0, half, 0);
dfs2(half, N, 0);
if (S == 0) --result;
cout << result;
return 0;
}프로그래머스 - 파괴되지 않은 건물 (누적합)
더보기
#include <iostream>
#include <vector>
using namespace std;
int solution(vector<vector<int>> board, vector<vector<int>> skill) {
int answer = 0;
int columnSize = board.size();
int rowSize = board[0].size();
vector <vector<int>> sums(columnSize + 2, vector<int>(rowSize + 2, 0));
for(auto q : skill)
{
const int val = q[5] * (q[0] == 1 ? -1 : 1);
const int r1 = q[1] + 1, c1 = q[2] + 1, r2 = q[3] + 1, c2 = q[4] + 1;
sums[r1][c1] += val;
sums[r2 + 1][c2 + 1] += val;
sums[r2 + 1][c1] -= val;
sums[r1][c2 + 1] -= val;
}
for (int c = 1; c <= columnSize; ++c)
for (int r = 1; r <= rowSize; ++r)
{
sums[c][r] = sums[c][r] + sums[c - 1][r] + sums[c][r - 1] - sums[c - 1][r - 1];
if (board[c - 1][r - 1] + sums[c][r] >= 1)
++answer;
}
return answer;
}프로그래머스 - k진수에서 소수 개수 구하기 (lv2)
더보기
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
bool IsPrime(long long n)
{
if (n <= 1) return false;
if (n == 2) return true;
if (n % 2 == 0) return false;
const long long sqrtn = (long long)sqrt(n);
for (long long i = 3; i <= sqrtn; i += 2)
if (n%i == 0) return false;
return true;
}
int solution(int n, int k) {
//k진수로 뽑아냄. 역순으로 저장됨
vector<int> mods;
while (n != 0)
{
mods.emplace_back(n%k);
n /= k;
}
//역순으로 저장된 k진수에서 숫자를 뽑아냄
vector<long long> nums;
long long cur = 0;
for (int i = mods.size() - 1; i >= 0; --i)
{
if (mods[i] == 0)
{
if (cur > 1)
nums.emplace_back(cur);
cur = 0;
}
else
cur = cur * 10 + mods[i];
}
if (cur > 1)
nums.emplace_back(cur);
//숫자가 소수인지 판별
int answer = 0;
for (auto num : nums) //auto 대신 int써서 1시간 참교육당함
if (IsPrime(num))
++answer;
return answer;
}
int main()
{
cout << solution(524287, 2) << endl;
}프로그래머스 - 주차 요금 계산
더보기
#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;
class ParkManager
{
public:
//time부터 23:59까지 시간 더해줌
void In(int carIdx, int time)
{
carTimeTotal[carIdx] += BaseExitTime_ - time;
}
//time에서 23:59까지 시간 빼줌
void Out(int carIdx, int time)
{
carTimeTotal[carIdx] -= BaseExitTime_ - time;
}
vector<pair<int,int>> GetSortedCarTimes()
{
vector<pair<int, int>> sortedCarTimes;
sortedCarTimes.reserve(carTimeTotal.size());
for(auto carTime : carTimeTotal)
{
sortedCarTimes.emplace_back(make_pair(carTime.first, carTime.second));
}
sort(sortedCarTimes.begin(), sortedCarTimes.end());
return sortedCarTimes;
}
private:
const int BaseExitTime_ = 23 * 60 + 59;
unordered_map<int, int> carTimeTotal; //차량번호,
};
vector<int> solution(vector<int> fees, vector<string> records) {
vector<int> answer;
const int baseTime = fees[0];
const int baseFee = fees[1];
const int unitTime = fees[2];
const int unitFee = fees[3];
ParkManager mgr;
for(auto & r : records)
{
const int time = stoi(r.substr(0, 2)) * 60 + stoi(r.substr(3, 2));
const int carIdx = stoi(r.substr(6, 4));
if(r[11] == 'I')
mgr.In(carIdx, time);
else
mgr.Out(carIdx, time);
}
auto carTimes = mgr.GetSortedCarTimes();
for(auto times : carTimes)
{
int fee = baseFee;
if (times.second > baseTime)
{
fee += (times.second - baseTime) / unitTime * unitFee;
if ((times.second - baseTime) % unitTime != 0)
fee += unitFee;
}
answer.emplace_back(fee);
}
return answer;
}