Submission #379063

#	Time	Username	Problem	Language	Result	Execution time	Memory
379063		urd05	Naan (JOI19_naan)	C++14	100 / 100	763 ms	100844 KiB

naan

#include <bits/stdc++.h>
using namespace std;

int arr[2000][2000];
typedef pair<long long,long long> P; //first/second
typedef pair<P,int> Pi;
bool used[2000];

bool comp(Pi a,Pi b) {
    return (__int128)a.first.first*b.first.second<(__int128)b.first.first*a.first.second;
}

P save[2000][2000];

int main(void) {
    int n,l;
    scanf("%d %d",&n,&l);
    for(int i=0;i<n;i++) {
        for(int j=0;j<l;j++) {
            scanf("%d",&arr[i][j]);
        }
    }
    for(int i=0;i<n;i++) {
        int ind=1;
        long long sum=0;
        for(int j=0;j<l;j++) {
            sum+=arr[i][j];
        }
        long long temp=0;
        for(int j=0;j<l;j++) {
            while (ind<n&&(temp+arr[i][j])*n>=sum*ind) {
                save[i][ind]=P(sum*ind-n*temp+j*1LL*n*arr[i][j],n*arr[i][j]);
                ind++;
            }
            temp+=arr[i][j];
        }
    }
    vector<P> ret;
    vector<int> v;
    for(int cnt=n-1;cnt>0;cnt--) {
        vector<Pi> vec;
        for(int i=0;i<n;i++) {
            if (!used[i]) {
                vec.push_back(Pi(save[i][cnt],i));
            }
        }
        sort(vec.begin(),vec.end(),comp);
        reverse(vec.begin(),vec.end());
        used[vec[0].second]=true;
        v.push_back(vec[0].second);
        ret.push_back(vec[0].first);
    }
    reverse(ret.begin(),ret.end());
    for(int i=0;i<n;i++) {
        if (!used[i]) {
            v.push_back(i);
        }
    }
    reverse(v.begin(),v.end());
    for(int i=0;i<ret.size();i++) {
        printf("%lld %lld\n",ret[i].first,ret[i].second);
    }
    for(int i=0;i<v.size();i++) {
        printf("%d ",v[i]+1);
    }
}

Compilation message (stderr)

naan.cpp: In function 'int main()':
naan.cpp:60:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for(int i=0;i<ret.size();i++) {
      |                 ~^~~~~~~~~~~
naan.cpp:63:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for(int i=0;i<v.size();i++) {
      |                 ~^~~~~~~~~
naan.cpp:17:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   17 |     scanf("%d %d",&n,&l);
      |     ~~~~~^~~~~~~~~~~~~~~
naan.cpp:20:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   20 |             scanf("%d",&arr[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~~

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