Submission #826766

#	Time	Username	Problem	Language	Result	Execution time	Memory
826766		Charizard2021	Naan (JOI19_naan)	C++17	100 / 100	838 ms	147660 KiB

naan

#include <bits/stdc++.h>
using namespace std;
bool operator <(pair<long long, long long> a, pair<long long, long long> b){
    return (__int128)a.first * b.second < (__int128)a.second * b.first;
}
int main(){
    long long n, m;
    cin >> n >> m;
    vector<long long> a(n);
    long long grid[n][m];
    long long pref[n][m];
    for(long long i = 0; i < n; i++){
        for(long long j = 0; j < m; j++){
            cin >> grid[i][j];
            grid[i][j] *= n;
            a[i] += grid[i][j];
        }
        a[i] /= n;
    }
    for(long long i = 0; i < n; i++){
        pref[i][0] = grid[i][0];
        for(long long j = 1; j < m; j++){
            pref[i][j] = pref[i][j - 1] + grid[i][j];
        }
    }
    vector<bool> visited(n, false);
    vector<vector<pair<long long, long long> > > val(n, vector<pair<long long, long long> >(n));
    for(long long i = 0; i < n; i++){
        long long cur = 0;
        long long idx2 = 0;
        for(long long j = 0; j < n - 1; j++){
            cur += a[i];
            while(idx2 < m && pref[i][idx2] < cur){
                idx2++;
            }
            long long val2 = 0;
            if(idx2 > 0){
                val2 = pref[i][idx2 - 1];
            }
            val[i][j] = make_pair(cur - val2 + idx2 * grid[i][idx2], grid[i][idx2]);
        }
    }
    vector<long long> res(n);
    for(long long i = 0; i < n - 1; i++){
        long long idx = -1;
        for(long long j = 0; j < n; j++){
            if(!visited[j]){
                if(idx == -1){
                    idx = j;
                }
                else if(val[j][i] < val[idx][i]){
                    idx = j;
                }
            }
        }
        res[i] = idx + 1;
        visited[idx] = true;
        cout << val[idx][i].first << " " << val[idx][i].second << "\n";
    }
    for(long long i = 0; i < n; i++){
        if(!visited[i]){
            res[n - 1] = i + 1;
        }
    }
    for(long long j = 0; j < n; j++){
        cout << res[j] << " ";
    }
    cout << "\n";
    return 0;
}

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