(200731)나도 코드포스

Codeforces materials usage license (v. 0.1) 에 따라 codeforces.com 의 문제임을 알립니다.

original problem link: Round #653(div.3) E Reading Books (easy version)

Example

Input

8 4
7 1 1
2 1 1
4 0 1
8 1 1
1 0 1
1 1 1
1 0 1
3 0 0

Output

18

Input

5 2
6 0 0
9 0 0
1 0 1
2 1 1
5 1 0

Output

8

Input

5 3
3 0 0
2 1 0
3 1 0
5 0 1
3 0 1

Output

-1

그때 가상 참여하던거 마져 풀었는데 재미있네요
E1 E2 난이도 차이 무엇;;

3 Likes
E1
#include "bits/stdc++.h"

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    priority_queue<int, vector<int>, greater<int>> both;
    priority_queue<int, vector<int>, greater<int>> alice;
    priority_queue<int, vector<int>, greater<int>> bob;
    for (int i = 0; i < n; i++) {
        int t, a, b;
        cin >> t >> a >> b;
        if (a & b)
            both.push(t);
        else if (a)
            alice.push(t);
        else if (b)
            bob.push(t);
    }

    int time = 0;
    for (int i = 0; i < k; i++) {
        if (both.empty()) {
            if (alice.empty() || bob.empty()) {
                cout << -1;
                return 0;
            } else {
                time += alice.top();
                time += bob.top();
                alice.pop();
                bob.pop();
            }
        } else {
            if (alice.empty() || bob.empty() || both.top() < alice.top() + bob.top()) {
                time += both.top();
                both.pop();
            } else {
                time += alice.top();
                time += bob.top();
                alice.pop();
                bob.pop();
            }
        }
    }
    cout << time;
    return 0;
}

에디토리얼 보고 왔는데
에디토리얼은 항상 희안하게 푸는 듯? ㅋㅋㅋㅋ
각 종류 별로 소트 후 prefix sum 해서 편하게 계산하고
안되는 케이스도 잘 처리했네요.

:smile: 조쿤요. 헌데, @penzer27 님이 사라졋네요. :thinking:

1 Like

어디가셨지 저도 궁금합니다.
일이 바쁜가봐요

물난리를 겪고계시진 않길 바라면서, 이제 아우타스카이님이 매일 풀이 올려주신다니 참 기대가 됩니다.

사실 동일인물이였던 것…?

아 너모 무섭다. :fearful:

1 Like

@sh @outersky
ㅋㅋㅋ 어제 골아떨어졌어융.
문제 풀려고 알람 맞춰놓고 자긴 해서 깨긴 했는데 고민하다가 더 잤습니다.
하루 충전했으니 주말 동안 하루에 difficult 1700 이상 5문제 이상씩 풀어재끼겠읍니다. :slight_smile:

저도 이 문제 풀어봐야겠네용. ㅎㅎ

1 Like

그런거 였군요~ 다행입니다.

1 Like

9986C2375C47897710

자가분석결과 아마 지금 절망의 계곡에 있는듯합니다. 계속해야겠지요. ㅎㅎ

봉우리위에서 행복해하고있는 저도 있어요. 님 화이팅~

저 그래프 볼때마다 마이너스가 없어서 허전한것 같습니다. 분명히 모를때 보다 밑으로 가는거 엄청 쉬운일인것 같은데

1 Like

까딱하면 매일 풀뻔 했는데 일일 5솔이라니 바톤회수 감사합니다

1 Like

전에랑 똑같은 방식으로 풀었군요. 코드는 조금 깔끔해진 것 같습니다.
아우타님은 그 자료구조를 쓰셨군요 ㅋㅋ 느리네요 아무래도 I/O가

1374E1 200703 Solution

namespace {
using namespace std;
}  // unnamed namespace;
 
int main(int argc, char** argv) {
  INIT_CODEFORCES();
 
  int n, k;
 
  cin >> n >> k;
 
  vector<int> both;
  vector<int> alice;
  vector<int> bob;
 
  while (n--) {
    int t, a, b;
    cin >> t >> a >> b;
    if (a == 1 && b == 1) {
      both.emplace_back(t);
    } else if (a == 1) {
      alice.emplace_back(t);
    } else if (b == 1) {
      bob.emplace_back(t);
    }
  }
 
  sort(both.begin(), both.end());
  sort(alice.begin(), alice.end());
  sort(bob.begin(), bob.end());
 
  int both_index = 0;
  int alice_index = 0;
  int bob_index = 0;
  int ans = 0;
  while (k--) {
    if (both_index < both.size()) {
      if (alice_index < alice.size() &&
          bob_index < bob.size() && 
          alice[alice_index] + bob[bob_index] < both[both_index]) {
        ans += alice[alice_index++] + bob[bob_index++];  
      } else {
        ans += both[both_index++];
      }
    } else if (alice_index < alice.size() && bob_index < bob.size()) {
      ans += alice[alice_index++] + bob[bob_index++];
    } else {
      ans = -1;
      break;
    }
  }
 
  LOG_INFO << ans;
 
  return 0;
}
1374E1 오늘 솔루션
namespace {
using namespace std;

constexpr bool kMultiTestCase = false;
using Solver = predefined::Solver<kMultiTestCase>;

}  // unnamed namespace;

void solve() {
  int n, k;
  cin >> n >> k;

  vector<int> a_only;
  vector<int> b_only;
  vector<int> both;

  while(n--) {
    int t, a, b;
    cin >> t >> a >> b;

    if (a && b) both.push_back(t);
    else if (a) a_only.push_back(t);
    else if (b) b_only.push_back(t);
  }
  if (a_only.size() + both.size() < k ||
      b_only.size() + both.size() < k) {
    LOG_INFO << -1;
    return;
  }

  sort(a_only.begin(), a_only.end());
  sort(b_only.begin(), b_only.end());
  sort(both.begin(), both.end());

  auto a_only_iter = a_only.begin();
  auto b_only_iter = b_only.begin();
  auto both_iter = both.begin();

  int ans = 0;
  while (k--) {
    if (both_iter == both.end()) {
      ans += *(a_only_iter++) + *(b_only_iter++);
      continue;
    } else if ((a_only_iter == a_only.end()) || (b_only_iter == b_only.end())) {
      ans += *(both_iter++);
      continue;
    } 

    if (*a_only_iter + *b_only_iter < *both_iter) {
      ans += *(a_only_iter++) + *(b_only_iter++);
    } else {
      ans += *(both_iter++);
    }
  }

  LOG_INFO << ans;
}

int main(int argc, char** argv) {
  INIT_CODEFORCES();

  Solver([](){solve();});

  return 0;
}

???: @outersky 니 팀 버려!? 니 팀 버려?!

1 Like

사람 생각하는게 다 비슷비슷 하군요

저는 첨에 pair<int,pair<int,int>> 해서 sort에 less함수를 람다로 어떻게 잘 줘볼까 고민하다가 그냥 저거 썼네요 여기까지 댓글 내려 보시는 분은 스포 방지는 안중요하다 생각해서 그냥 씁니당

요 코드도 예쁘네요

니 팀 버려가 유튜브 유행어였군요.
안 버리고 종종 코포 하겠어요

1 Like