Submission #209161

#	Time	Username	Problem	Language	Result	Execution time	Memory
209161		achibasadzishvili	Naan (JOI19_naan)	C++17	100 / 100	631 ms	150368 KiB

naan

#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pb push_back
#define mp make_pair
using namespace std;
ll n,l,v[2003][2003],ans[2003],fix[2003];
vector<pair<pair<ll,ll> , ll> >g[2003];
__int128 a,b,c,d;
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> l;
    
    for(int i=1; i<=n; i++){
        ll sum = 0;
        for(int j=1; j<=l; j++){
            cin >> v[i][j];
            sum += v[i][j];
        }
        ll cur = 1 , don = 0 , cnt = 0;
        for(int j=1; j<=l; j++){
            //cout << i << "<-->" << j << " " << cur << " " << cnt << '\n';
            while((cnt + v[i][j]) * n >= cur * sum){
                g[cur].pb(mp(mp((j - 1) * v[i][j] * n + (cur * sum - cnt * n) , v[i][j] * n) , i));
                //cout << i << " " << cur << " " << (j - 1) * v[i][j] * n + (cur * sum - cnt * n) << " " << v[i][j] * n << '\n';
                cur++;
            }
            cnt += v[i][j];
        }
    }
    
    for(int i=1; i<n; i++){
        ll mna = 100000000000000000 , mnb = 1 , ind = -1;
        for(int j=0; j<g[i].size(); j++){
            if(fix[g[i][j].s])continue;
            a = mna;
            b = mnb;
            c = g[i][j].f.f;
            d = g[i][j].f.s;
            a *= d;
            c *= b;
            if(a > c){
                mna = g[i][j].f.f;
                mnb = g[i][j].f.s;
                ind = g[i][j].s;
            }
        }
        ans[i] = ind;
        fix[ind] = 1;
        cout << mna << " " << mnb << '\n';
    }
    
    for(int i=1; i<=n; i++)
        if(!fix[i])ans[n] = i;
        
    for(int i=1; i<=n; i++)
        cout << ans[i] << " ";
    
    
    
    return 0;
}

Compilation message (stderr)

naan.cpp: In function 'int main()':
naan.cpp:21:22: warning: unused variable 'don' [-Wunused-variable]
         ll cur = 1 , don = 0 , cnt = 0;
                      ^~~
naan.cpp:35:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0; j<g[i].size(); j++){
                      ~^~~~~~~~~~~~

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