Submission #902730


Source Code Expand

#include <iostream>
#include <vector>


using namespace std;


int main()
{
    //入力
    int N;
    cin >> N;

    vector<int> a;
    for( int i = 0; i < N; ++i ){
        int tmp;
        cin >> tmp;
        a.push_back(tmp);
    }


    int flag = 0, sum = 0, goal = 0, ans = 0;


    //そもそも,すべての島に同じ人数の住人が住んでいないか?
    flag = 0;
    for( int i = 0; i < N-1; ++i ){
        if( a[i] == a[i+1] ) ++flag;
    }
    if( flag == N-1 ){ //住んでいた
        cout << 0<< endl;
        return 0;
    }


    //そもそも,すべての島に同じ人数の住人が住めるか?
    sum = 0;
    for( int i = 0; i < N; ++i ){
        sum += a[i];
    }
    if( sum % N != 0 ){ //できない
        cout << -1 << endl;
        return 0;
    }


    //すべての島に同じ人数の住人が住めるらしい
    goal = sum / N; //各島の目標住人数
    for( int i = 0; i < N-1; ++i ){
        //右端の島から順に,負の住人数を許しながら,目標住人数にする
        if( a[i] != goal ){
            ++ans;
            int tmp = goal - a[i];
            a[i  ] += tmp;
            a[i+1] -= tmp;
        }
    }

    
    cout << ans << endl;


    return 0;
}

Submission Info

Submission Time
Task B - 島と橋
User canon4444
Language C++ (GCC 4.9.2)
Score 100
Code Size 1320 Byte
Status AC
Exec Time 20 ms
Memory 928 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 4
AC × 38
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt
All sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt, subtask1_30.txt, subtask1_31.txt, subtask1_32.txt, subtask1_33.txt, subtask1_34.txt
Case Name Status Exec Time Memory
sample_01.txt AC 17 ms 928 KB
sample_02.txt AC 17 ms 800 KB
sample_03.txt AC 17 ms 796 KB
sample_04.txt AC 17 ms 792 KB
subtask1_01.txt AC 18 ms 924 KB
subtask1_02.txt AC 19 ms 928 KB
subtask1_03.txt AC 17 ms 928 KB
subtask1_04.txt AC 17 ms 796 KB
subtask1_05.txt AC 17 ms 928 KB
subtask1_06.txt AC 17 ms 920 KB
subtask1_07.txt AC 17 ms 796 KB
subtask1_08.txt AC 17 ms 800 KB
subtask1_09.txt AC 17 ms 924 KB
subtask1_10.txt AC 19 ms 800 KB
subtask1_11.txt AC 19 ms 920 KB
subtask1_12.txt AC 17 ms 924 KB
subtask1_13.txt AC 17 ms 928 KB
subtask1_14.txt AC 19 ms 796 KB
subtask1_15.txt AC 19 ms 796 KB
subtask1_16.txt AC 17 ms 924 KB
subtask1_17.txt AC 17 ms 928 KB
subtask1_18.txt AC 18 ms 920 KB
subtask1_19.txt AC 18 ms 928 KB
subtask1_20.txt AC 17 ms 800 KB
subtask1_21.txt AC 19 ms 796 KB
subtask1_22.txt AC 19 ms 928 KB
subtask1_23.txt AC 19 ms 800 KB
subtask1_24.txt AC 19 ms 800 KB
subtask1_25.txt AC 19 ms 800 KB
subtask1_26.txt AC 18 ms 924 KB
subtask1_27.txt AC 20 ms 732 KB
subtask1_28.txt AC 17 ms 676 KB
subtask1_29.txt AC 17 ms 796 KB
subtask1_30.txt AC 19 ms 928 KB
subtask1_31.txt AC 18 ms 800 KB
subtask1_32.txt AC 17 ms 920 KB
subtask1_33.txt AC 19 ms 928 KB
subtask1_34.txt AC 17 ms 792 KB