Submission #1272373

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272373		tvgk	Naan (JOI19_naan)	C++20	0 / 100	2 ms	576 KiB

naan

#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define ll long long
#define fi first
#define se second
#define ii pair<ll, ll>
const int mxN = 2e3 + 7, inf = 1e9;

int n, m, mm;
ll sum[mxN], a[mxN][mxN], tmp[mxN];
bool ers[mxN];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie();
    cout.tie();
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);

    cin >> n >> m;
    mm = n;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> a[i][j];
            sum[i] += a[i][j];
        }
        sum[i] *= mm / n;
    }

    ii cur = {1, 0};
    vector<ii> ans;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
            tmp[j] = sum[j];

        vector<int> pos;
        while (pos.empty() && cur.fi <= m)
        {
            for (int j = 1; j <= n; j++)
            {
                if (ers[j])
                    continue;

                if (a[j][cur.fi] * (mm - cur.se) >= tmp[j])
                    pos.push_back(j);
                else
                    tmp[j] -= a[j][cur.fi] * (mm - cur.se);
            }

            if (pos.empty())
            {
                cur.fi++;
                cur.se = 0;
            }
        }

        if (pos.empty())
        {
            cout << -1;
            return 0;
        }

        ii mn = {inf, inf};
        for (int i : pos)
            mn = min(mn, {(tmp[i] + a[i][cur.fi] - 1) / a[i][cur.fi], i});

        cur.se += mn.fi;
        if (cur.se == mm)
        {
            cur.fi++;
            cur.se = 0;
        }
        ers[mn.se] = 1;

        ans.push_back({(cur.fi - 1) * mm + cur.se, mn.se});
    }

    for (int i = 0; i < ans.size() - 1; i++)
        cout << ans[i].fi << " " << mm << '\n';
    for (ii i : ans)
        cout << i.se << " ";
}

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