Submission #2997997


Source Code Expand

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

#define NDEBUG
#ifdef DEBUG
#include "../cout11.h"
#undef NDEBUG
#endif
#include <cassert>

typedef long long ll;
typedef long double Double;
typedef unsigned long long ull;
typedef pair<int,int> ii;
typedef pair<ll,ll> llll;
typedef pair<double,double> dd;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<long double> vD;

#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);++var)
#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define ALL(c)  (c).begin(),(c).end()
#define RALL(c)  (c).rbegin(),(c).rend()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())
#define mset(arr,val)  memset(arr,val,sizeof(arr))
#define mid(x,y) ((x)+((y)-(x))/2)
#define IN(x,a,b) ((a)<=(x)&&(x)<=(b))
#define cons make_pair


pair<ll, ll> min_max(vector<ll>& a) {
    ll amin = LLONG_MAX, amax = LLONG_MIN;
    for (int i=a.size()-1; i>=0; --i) {
        amin = min(amin, a[i]);
        amax = max(amax, a[i]);
    }
    return make_pair(amin, amax);
}

ll solve(ll N, vector<ll>& a) {
    ll ans =0;
    while (true) {
        auto amm = min_max(a);
        ll amin = amm.first, amax = amm.second;
        if (amax <= N-1) break;

        ll s = 0;
        rep(i, N) {
            s += a[i] / N;
        }
        ans += s;
        rep(i, N) {
            ll q = a[i] / N;
            a[i] = a[i] - q*N + (s - q);
        }
    }
    return ans;
}

int main() {
    int N; cin >> N;
    vector<ll> a(N);
    rep(i, N) cin >> a[i];
    cout << solve(N,a) << endl;
    return 0;
}

Submission Info

Submission Time
Task E - Decrease (Judge ver.)
User naoya_t
Language C++14 (GCC 5.4.1)
Score 600
Code Size 2009 Byte
Status
Exec Time 3 ms
Memory 256 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 example0, example1, example2, example3, example4
All 600 / 600 example0, example1, example2, example3, example4, maxrand0, maxrand1, maxrand2, maxrand3, maxrand4, maxrand5, maxrand6, maxrand7, maxrand8, maxrand9, rand0, rand1, rand2, rand3, rand4, rand5, rand6, rand7, rand8, rand9, small0, small1, small2, small3, small4, small5, small6, small7, small8, small9
Case Name Status Exec Time Memory
example0 1 ms 256 KB
example1 1 ms 256 KB
example2 1 ms 256 KB
example3 1 ms 256 KB
example4 1 ms 256 KB
maxrand0 1 ms 256 KB
maxrand1 3 ms 256 KB
maxrand2 1 ms 256 KB
maxrand3 3 ms 256 KB
maxrand4 1 ms 256 KB
maxrand5 3 ms 256 KB
maxrand6 1 ms 256 KB
maxrand7 3 ms 256 KB
maxrand8 1 ms 256 KB
maxrand9 3 ms 256 KB
rand0 1 ms 256 KB
rand1 1 ms 256 KB
rand2 2 ms 256 KB
rand3 2 ms 256 KB
rand4 1 ms 256 KB
rand5 1 ms 256 KB
rand6 1 ms 256 KB
rand7 2 ms 256 KB
rand8 1 ms 256 KB
rand9 2 ms 256 KB
small0 1 ms 256 KB
small1 1 ms 256 KB
small2 1 ms 256 KB
small3 1 ms 256 KB
small4 1 ms 256 KB
small5 1 ms 256 KB
small6 1 ms 256 KB
small7 1 ms 256 KB
small8 1 ms 256 KB
small9 1 ms 256 KB