Submission #1169902

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169902		user736482	Naan (JOI19_naan)	C++20	5 / 100	0 ms	584 KiB

naan

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#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

ll n,k,a,b,c;
vector<ll>koszty[2007];
vector<ll>vpom;
ll czyje[2007],sm[2007],akkk[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;
    for(ll i=0;i<n;i++){
        for(ll j=0;j<k;j++){
            cin>>a;
            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";
        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]={k-1,1};
            ll akk=akkk[i];
            ll nxt=k-1;
            while(akk*n<sm[i] && akk+koszty[i][nxt]<=sm[i]/n){
                akwyn[i].ff--;
                akk+=koszty[i][nxt];
                nxt--;
            }
            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;
           /* ll pom=akwyn[i].ff/akwyn[i].ss;
            if(sm[i]<(akwyn[i].ff-pom*akwyn[i].ss)){
                akwyn[i].ff-=sm[i];
            }
            else{

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

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