Submission #1038220

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038220		juicy	Naan (JOI19_naan)	C++17	100 / 100	249 ms	101204 KiB

naan

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 2e3 + 5;

int n, l;
int a[N][N], res[N];
bool vs[N];
array<long long, 2> cut[N][N], ans[N];

bool cmp(const array<long long, 2> &a, const array<long long, 2> &b) {
  return (__int128_t) a[0] * b[1] < (__int128_t) a[1] * b[0];
}

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

  cin >> n >> l;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= l; ++j) {
      cin >> a[i][j];
    }
  }
  for (int i = 1; i <= n; ++i) {
    long long tot = accumulate(a[i] + 1, a[i] + l + 1, 0LL), cur = 0;
    cut[i][0] = {0, 1};
    for (int j = 1, k = 0; j < n; ++j) {
      while (cur + (long long) a[i][k + 1] * n <= tot * j) {
        cur += (long long) a[i][++k] * n;
      }
      cut[i][j] = {tot * j - cur, (long long) a[i][k + 1] * n};
      cut[i][j][0] += (long long) k * a[i][k + 1] * n;
    }
    cut[i][n] = {l, 1};
  }
  for (int i = 1; i <= n; ++i) {
    int best = 0;
    for (int j = 1; j <= n; ++j) {
      if (!vs[j] && (best == 0 || cmp(cut[j][i], cut[best][i]))) {
        best = j;
      }
    }
    vs[best] = 1;
    res[i] = best;
    ans[i] = cut[best][i];
  }
  for (int i = 1; i < n; ++i) {
    cout << ans[i][0] << " " << ans[i][1] << "\n";
  }
  for (int i = 1; i <= n; ++i) {
    cout << res[i] << " ";
  }
  return 0;
}

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