Submission #881447

#	Time	Username	Problem	Language	Result	Execution time	Memory
881447		nima_aryan	Naan (JOI19_naan)	C++17	100 / 100	320 ms	111408 KiB

naan

/**
 *    author:  NimaAryan
 *    created: 2023-12-01 08:14:38  
**/
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#endif

using i64 = long long;
using i128 = __int128;

constexpr i64 inf = 1E14;

struct Z {
  i64 A = 0;
  i64 B = 1;

  Z() { }
  Z(i64 A, i64 B) : A(A), B(B) { }

  bool operator<(const Z& other) const {
    return (i128) A * other.B < (i128) other.A * B;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int N, L;
  cin >> N >> L;

  vector V(N, vector<i64>(L));
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < L; ++j) {
      cin >> V[i][j];
    }
  }

  vector C(N, vector<Z>(N));
  for (int i = 0; i < N; ++i) {
    i64 sum = accumulate(V[i].begin(), V[i].end(), 0LL);
    i64 pref = 0;
    Z res{};

    for (int j = 0, k = 0; j < N; ++j) {
      while (k < L && Z(pref, j + 1) < Z(sum, N)) {
        pref += V[i][k++];
      }

      if (Z(k, 1) < res) {
        res.A += sum;
      } else {
        res = Z(1LL * N * V[i][k - 1] * (k - 1) + sum * (j + 1) - N * (pref - V[i][k - 1]), N * V[i][k - 1]);
      }

      C[i][j] = res;
    }
  }

  vector<Z> H;
  vector<bool> used(N);
  vector<int> P;
  for (int j = 0; j < N; ++j) {
    Z best(inf, 1);
    int who = -1;

    for (int i = 0; i < N; ++i) {
      if (!used[i] && C[i][j] < best) {
        tie(best, who) = pair(C[i][j], i);
      }
    }

    H.push_back(best);
    P.push_back(who);
    used[who] = true;
  }

  for (int i = 0; i < N - 1; ++i) {
    cout << H[i].A << " " << H[i].B << "\n";
  }
  for (int i = 0; i < N; ++i) {
    cout << P[i] + 1 << " \n"[i + 1 == N];
  }
  return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 24 / 24
• Subtask 3: 71 / 71