Submission #1169950

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169950		user736482	Naan (JOI19_naan)	C++20	100 / 100	275 ms	64992 KiB

naan

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll __int128
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 998244353
#define POT 4194304
#define INF 1000000019
#define INFL 1000000000000000099LL
long long lll;
ll n,k,a,b,c;
vector<ll>koszty[2007];
vector<ll>vpom;
ll czyje[2007],sm[2007],akkk[2007],nxtt[2007];
pair<ll,ll>akwyn[2007];
pair<ll,ll>gdzie[2007];//ulamek

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
 //   cin>>n>>k;
 cin>>lll;
 n=lll;
 cin>>lll;
 k=lll;
    for(ll i=0;i<n;i++){
        for(ll j=0;j<k;j++){
            //cin>>a;
               cin>>lll;
            a=lll;
           // a=rand()%100000 +1 ;
            sm[i]+=a;
            koszty[i].pb(a);
        }
        vpom.pb(i);
    }
    for(ll i=0;i<n;i++){
        akwyn[i]={k-1,1};
        ll akk=0;
        ll nxt=k-1;
     //   cout<<akk+koszty[i][nxt]<<" "<<sm[i]/n<<" ";
        while(akk*n<sm[i] && akk+koszty[i][nxt]<=sm[i]/n){
            akwyn[i].ff--;
            akk+=koszty[i][nxt];
     //       cout<<akk<<" "; 
            nxt--;
        }
   //     cout<<"\n";
        akwyn[i]={(-sm[i]+akk*n+n*koszty[i][nxt]*(akwyn[i].ff+1)),(n*koszty[i][nxt])};
       // cout<<akwyn[i].ff<<" "<<akwyn[i].ss<<"\n\n";
       nxtt[i]=nxt;
        akkk[i]=akk;
    }
    while(vpom.size()>1){
        pair<ll,ll>mx={0,INF};
        ll bst=-1;
        for(ll i : vpom){
            if(akwyn[i].ff*mx.ss>=akwyn[i].ss*mx.ff){
                bst=i;
                mx=akwyn[i];
            }
        }
        gdzie[vpom.size()-2]=mx;
        czyje[vpom.size()-1]=bst;
        //cout<<bst<<" ";
        vpom.erase(find(vpom.begin(),vpom.end(),bst));
        for(ll i:vpom){
            akwyn[i]={nxtt[i],1};
            ll akk=akkk[i];
            ll nxt=nxtt[i];
            while(akk*n<sm[i]*(n+1-vpom.size()) && akk+koszty[i][nxt]<=sm[i]*(n+1-vpom.size())/n){
                akwyn[i].ff--;
                akk+=koszty[i][nxt];
                nxt--;
            }
           // cout<<akwyn[i].ff<<" "<<akwyn[i].ss<<"   ";
            akwyn[i]={(-sm[i]*(n+1-vpom.size())+akk*n+n*koszty[i][nxt]*(akwyn[i].ff+1)),(n*koszty[i][nxt])};
            akkk[i]=akk;
            nxtt[i]=nxt;
            
           /* ll pom=akwyn[i].ff/akwyn[i].ss;
            if(sm[i]<(akwyn[i].ff-pom*akwyn[i].ss)){
                akwyn[i].ff-=sm[i];
            }
            else{

            }*/
        }
      //  cout<<"\n";
   }
   czyje[0]=vpom[0];
   for(ll i=0;i+1<n;i++)
    cout<<(long long)gdzie[i].ff<<" "<<(long long)gdzie[i].ss<<"\n";
for(ll i=0;i+2<n;i++){
    if(gdzie[i].ff*gdzie[i+1].ss>gdzie[i+1].ss*gdzie[i].ff)
        cout<<(long long)i<<"xd";
}
   for(ll i=0;i<n;i++)
    cout<<(long long)czyje[i]+1<<" ";
}

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